第一次这么顺手。。。都是1A。。。。D想了1个小时，想了一个假算法。。。最后20分开E，我叼，简单DP？？？不负众望的10分钟A掉。。。
A. Yet Another Dividing into Teams 只会有两个队
B1.B2. Books Exchange直接DFS找环，环内的传递时间是一样的。标记一下，线性复杂度。
C1. Good Numbers (easy version) 其实就是3进制表示形式不能有2，那么简单版本直接预处理1-1000然后找第一个大于n的数即可。
#include<bits/stdc++.h> #define LL long long using namespace std; vector<int>ans; bool check(int x){ int flag=0; while(x){ if (x%3==2){ flag=1; break; } x=x/3; } if (flag==1)return 0; else return 1; } void init(){ for (int i=1;i<=19683;i++){ if(check(i)){ ans.push_back(i); } } } int main(){ int t,n; scanf("%d",&t); init(); while(t--){ scanf("%d",&n); int pos=lower_bound(ans.begin(),ans.end(),n)-ans.begin(); printf("%d ",ans[pos]); } return 0; }
C2. Good Numbers (hard version) 我们比较容易求出最大小于n的数，因为我们可以从3的高位往低位试。然后从地位到高位，把第一个3进制位为0的位置变成1，其后位置全部变成0，就是刚好大于等于n的三进制没有2的。
#include<bits/stdc++.h> #define LL long long using namespace std; LL n; LL qpow(LL a,LL b) { LL ans=1; while(b) { if(b&1) ans=ans*a; a=a*a; b=b/2; } return ans; } int vis[50]; int main() { int t; LL s=1e18; scanf("%d",&t); while(t--) { scanf("%lld",&n); LL ans=0; memset(vis,0,sizeof(vis)); for (int i=38;i>=0;i--) { if (ans+qpow(3,i)<n){ ans+=qpow(3,i); vis[i]=1; } } for (int i=0;i<=38;i++){ if (vis[i]==1){ ans-=qpow(3,i); }else { ans+=qpow(3,i); break; } } printf("%lld ",ans); } return 0; }
D1.D2. Too Many Segments 看错题了，我一直以为要保证整个区间是连续的。。。。发现其实只要区间的覆盖次数<k次就行，这样的话，其实就很简单了，把区间排序，放入一个mutilset里面，里面维护所有有相交区间的覆盖，然后判断mutilset是不是大于k个，如果是一定要丢，怎么丢比较优雅？？？反正最左边已经保证了覆盖次数<k，那么丢区间的右端点最远的，这样对后面影响也最小。
#include<bits/stdc++.h> #define pii pair<int,int> #define rep(i,j,k) for(int i=j;i<=k;i++) #define per(i,j,k) for(int i=j;i>=k;i--) #define mp make_pair #define pb push_back using namespace std; const int maxx = 2e5+6; multiset<pii>s; vector<int>ans; struct node{ int l,r,id; }p[maxx]; bool cmp(node a,node b){ return a.l<b.l; } int main(){ int n,k; while(~scanf("%d%d",&n,&k)){ for (int i=1;i<=n;i++){ scanf("%d%d",&p[i].l,&p[i].r); p[i].id=i; } ans.clear(); sort(p+1,p+1+n,cmp); rep(i,1,n){ ///s里面最小的r小于p[i].l代表两者已经不相连了 while(s.size() && (*s.begin()).first<p[i].l)s.erase(s.begin()); s.insert(mp(p[i].r,p[i].id)); ///这里s代表重复里面每一段都有重复部分 如果重复部分大于K了 ///肯定删除最右边的，因为最左边的已经满足小于k了，删除最右边的，使得后面出现>k的概率变小了 while(s.size()>k){ auto it=s.end(); it--; ans.pb((*it).second); s.erase(it); } } int sz=ans.size(); printf("%d ",sz); for (int i=0;i<sz;i++){ if(i)printf(" %d",ans[i]); else printf("%d",ans[i]); } printf(" "); } return 0; }
E.简单DP，每层一定是由上一层转移过来，所以很简单了。
#include<bits/stdc++.h> #define LL long long #define lson rt<<1 #define rson rt<<1|1 using namespace std; const int maxx = 2e5+6; LL a[maxx]; LL b[maxx]; LL n,c; LL dp[maxx][3]; int main(){ while(~scanf("%lld%lld",&n,&c)){ for (int i=2;i<=n;i++){ scanf("%lld",&a[i]); } for (int i=2;i<=n;i++){ scanf("%lld",&b[i]); } dp[1][1]=0; dp[1][2]=c; for (int i=2;i<=n;i++){ dp[i][1]=min(dp[i-1][1]+a[i],dp[i-1][2]+a[i]); dp[i][2]=min(dp[i-1][2]+b[i],dp[i-1][1]+b[i]+c); } for (int i=1;i<=n;i++){ if (i-1)printf(" %lld",min(dp[i][1],dp[i][2])); else printf("0"); } printf(" "); } }
F.真~神仙题，树有点权，问选出一个集合，使得集合内部所有点的距离>=k，并且点权和最大。。。
树形DP做法。。。看了2个小时自闭了。。。等牛逼网友发博客再说
贪心：我们考虑选择某个的贡献，我们首先安装深度从下往上进行遍历，然后对于每次选择i，我们把这个点所有距离<=k的点，减去a[i]，代表选择了这个点，如果某个点的值>0，代表这个点比i更优秀？？？我们可以直接加上a[j]代表选择j，由于我们算的是贡献，所以直接把周围的点的所有能到的点的全部减去即可。
#include<bits/stdc++.h> #define LL long long #define pii pair<int,int> #define mp make_pair #define pb push_back using namespace std; const int maxx = 1005; int ver[maxx],Next[maxx],head[maxx]; int vis[maxx]; int a[maxx]; int n,k,tot; vector<int>b; void add(int x,int y){ ver[++tot]=y;Next[tot]=head[x];head[x]=tot; ver[++tot]=x;Next[tot]=head[y];head[y]=tot; } void bfs(int st){ queue<pii>q; q.push(mp(st,0)); while(q.size()){ int u=q.front().first; int dep=q.front().second; b.pb(u); q.pop(); vis[u]=1; for (int i=head[u];i;i=Next[i]){ int v=ver[i]; if (!vis[v]){ q.push(mp(v,dep+1)); } } } } int dfs(int x){ for (int i=1;i<=n;i++){ vis[i]=0; } queue<pii>q; while(q.size())q.pop(); q.push(mp(x,0)); int c=a[x]; while(q.size()){ int u=q.front().first; a[u]-=c; vis[u]=1; int dep=q.front().second; q.pop(); for (int i=head[u];i;i=Next[i]){ int v=ver[i]; if (vis[v])continue; if (dep<k){ q.push(mp(v,dep+1)); } } } return c; } int main(){ while(~scanf("%d%d",&n,&k)){ for (int i=1;i<=n;i++){ scanf("%d",&a[i]); } int uu,vv; for (int i=1;i<n;i++){ scanf("%d%d",&uu,&vv); add(uu,vv); } bfs(1); reverse(b.begin(),b.end()); int sz=b.size(); int ans=0; for (int i=0;i<sz;i++){ if (a[b[i]]>0)ans+=dfs(b[i]); } printf("%d ",ans); } return 0; }