A Ehab and another construction problem
水题，不解释。
#include#include #include #include #include #include
B Ehab and subtraction
排个序扫一遍就好了。
#include#include #include #include #include #include
C Ehab and a 2-operation task
先用n次操作变成模n递增，然后直接模n即可。
#include#include #include #include #include #include
D Ehab and another another xor problem
这道题我的做法是这样的。
从高到低来枚举，先判断a,b从当前位开始的大小关系，如果a==b，那么直接计算每一位是什么即可。
否则，假设a<b，判断a和b异或当前位的大小关系，如果异或后a>b，那么说明a这一位为0，b这一位为1，然后再用一次判断来再次确定ab的大小关系。
如果异或后a<b，那么再判断a异或当前位与b的大小关系，如果异或后a>b，那么a，b这一位都是0，否则都是1。
如果a>b，反之即可。
#include#include #include #include #include #include
E Ehab and a component choosing problem
读错题了。。尴尬。我看成了选一个联通块，最大化点权和与点数的比值，还以为是01分数规划的板子，而且我还不会。。
实际上是让你选若干个联通块，最大化联通块点权和与联通块个数的比值。
那就先求出最大的联通块大小，然后贪心选就好了。。
#include#include #include using namespace std;typedef long long ll;const int Maxn=610000;int to[Maxn],nxt[Maxn],first[Maxn],tot=1;int ans,a[Maxn],n,u,v;ll sxz=0x8000000000000000;inline void add(int u,int v) { to[tot]=v; nxt[tot]=first[u]; first[u]=tot++; to[tot]=u; nxt[tot]=first[v]; first[v]=tot++;}ll dp1(int root,int fa) { ll zhy=a[root]; for(int i=first[root];i;i=nxt[i]) if(to[i]!=fa) zhy+=max(dp1(to[i],root),0ll); sxz=max(sxz,zhy); return zhy;}ll dp2(int root,int fa) { ll zhy=a[root]; for(int i=first[root];i;i=nxt[i]) if(to[i]!=fa) zhy+=max(dp2(to[i],root),0ll); if(zhy==sxz) { ans++; return 0; } return zhy;}int main() {// freopen("test.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i
F Ehab and a weird weight formula
大概就是有一个结论，就是如果把最小的点作为根，那么越往下点权越大，那就可以倍增一下，越往上要比没有跑到最上面要更优，那就dfs，依次更新所有的点，具体可以参考代码。
#include#include #include using namespace std;typedef long long ll;const int Maxn=1100000;int to[Maxn],nxt[Maxn],first[Maxn],tot=1;int f[Maxn][21],a[Maxn],n,u,v;ll ans;inline void add(int u,int v) { to[tot]=v; nxt[tot]=first[u]; first[u]=tot++; to[tot]=u; nxt[tot]=first[v]; first[v]=tot++;}void dfs(int root,int fa) { ll temp=0x7fffffffffffffff; for(int i=1;i<=20;i++) { temp=min(temp,1ll*i*a[f[root][i-1]]); f[root][i]=f[f[root][i-1]][i-1]; } temp+=a[root];if(root!=fa) ans+=temp; for(int i=first[root];i;i=nxt[i]) if(to[i]!=fa) { f[to[i]][0]=root; dfs(to[i],root); }}int main() {// freopen("test.in","r",stdin); scanf("%d",&n); a[0]=0x7fffffff;int root=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[root]>a[i]) root=i; } for(int i=1;i
看来还是自己太菜了啊，每次就能做4道题，每次都是第五题当时不会做一考完就想出来了，看来以后还是要多练习，一定要相信自己能做出来，冷静思考。