……
没什么说的了……
我感觉我多打打是有道理的,毕竟以前的蓝名也不是我的水平啊……虽然现在绿绿的很不爽
怕被hack多花了几分钟在A题上……浪费了几分.
B题水样例水完就PP,然后也没再检查,最终FST……
C题被自己的完全背包的内存吓到死推不出1e9的正解
D题困死……
第二天早上起来3分钟改完……
这次考试真的水……
所以我又一次考试只切了A题……wtmd
题目链接
大概意思就是要你求\(m%2^n\)的答案
题解
可以发现\(2^n\)次没有模数,所以即使开到了龙龙,\(n\)也只能到一个很小的值,可以直接判断如果\(n>30\)就输出\(m\),不然的话就计算\(2^n\)的答案再取模算一下就好了.
……计算\(2^n\)直接1<<n就好了……然后我写了个ksm……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> using namespace std ; template<class T>void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return ; } const int maxn=100010; #define LL long long LL n,m; LL ksm(LL a,LL b,LL ans=1){ while(b){ if(b&1) ans=ans*a; a=a*a;b>>=1; } return ans; } int main() { read(n),read(m); LL x=m,ans=0; while(x)x>>=1,ans++; if(n>=ans){printf("%lld\n",m);return 0;} printf("%lld",m%ksm(2,n)); return 0; } |
题目链接
题解
大概意思就是要你判断给定的一颗树是不是满足非叶子节点的叶子节点数大于等于3
然后注意维护的时候开好桶……记得判断一旦一个不满足就跳出输出NO……
FST的我真的没话了……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> using namespace std ; template<class T>void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return ; } const int maxn=1010; int n,ans,ecnt; int head[maxn],tong[maxn],lf[maxn]; int main() { read(n); for(int i=2;i<=n;i++){ read(head[i]);tong[head[i]]=1; } for(int i=2;i<=n;++i) if(!tong[i]) lf[head[i]]++; for(int i=1;i<=n;i++) if(tong[i]&&lf[i]<3) {puts("NO");return 0;} puts("YES"); return 0; } |
题目链接
大概意思就是需要买\(l\)升的饮料,超市有\(n\)种不同大小的饮料,给定价格\(c[i]\),第\(i\)种饮料有\(2^{i-1}\)升,问最小花费……
一眼不就是完全背包……
但是\(l<=10^9\)拿头去开背包……
本来以为这题显然动态规划……结果只是一个简单傻逼的贪心
我们按单位容量价值比排序.
直接买性价比最高的那个,然后需要一个小小的判断
可以理解为dp的转移……
剩余容量是在这个地方一次买完,还是选择换下一家买……
就切了……
wtmd
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> using namespace std ; template<class T>void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return ; } const int maxn=100; #define LL long long LL n,l; struct node{ LL val,cost; inline bool operator<(const node a){return (a.cost*val>a.val*cost);} }a[maxn]; LL dfs(LL lr,LL ct,LL num){ LL ccon=lr/a[num].val; ct+=ccon*a[num].cost; lr-=ccon*a[num].val; if(!lr) return ct; return min(ct+a[num].cost,dfs(lr,ct,num+1)); } int main() { read(n),read(l);read(a[1].cost);a[1].val=1; for(int i=2;i<=n;i++){ read(a[i].cost); a[i].val=a[i-1].val*2; } sort(a+1,a+1+n); printf("%lld\n",dfs(l,0,1)); return 0; } |
By:Wahacer
2018.1.9
14:21