Xor and Sum
之前做过一道异或的。感觉有点眼熟，发现不是。由于对异或一点也不熟悉。所以直接放弃了
首先写出来几项看看。
a: 1 2 4 1 1 2 4
prex : 1 3 7 6 7 5 1
prey: 1 3 7 8 9 11 15
可以发现如果区间异或和==区间和，那么缩小区间还是一样的。如果！=,那么扩大区间也是一样的。
所以可以枚举左端点，然后计算区间个数。
如果当前p和i满足，p++就是缩小区间，明显满足，所以可以省去，得出结果I-p。如果不满足，就找到一个满足点。当i=p，肯定满足。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=2e5+10; 4 5 int prex[maxn],prey[maxn]; 6 7 int main() { 8 int n; 9 while(~scanf("%d",&n)) { 10 for(int i=1;i<=n;i++) { 11 int x; 12 scanf("%d",&x); 13 prex[i]=prex[i-1]^x; 14 prey[i]=prey[i-1]+x; 15 } 16 int p=0; 17 long long ans=0; 18 for(int i=1;i<=n;i++) { 19 while((prex[i]^prex[p])!=prey[i]-prey[p]) p++; 20 ans+=i-p; 21 } 22 printf("%lld ",ans); 23 } 24 }
生命之树
比赛的时候跑了每一个青蛙节点，然后求都能到达的。其实只需要求最远的两个即可。也就是包含青蛙的树的直径。然后看能同时到达这两个节点的节点有多少个。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=100010; 4 5 int _,n,m,d,col[maxn],dis[maxn],newcol[maxn]; 6 vector<int> G[maxn]; 7 8 void dfs(int u,int p) { 9 dis[u]=dis[p]+1; 10 for(int i=0;i<G[u].size();i++) { 11 int v=G[u][i]; 12 if(v!=p) dfs(v,u); 13 } 14 } 15 16 int main() { 17 for(scanf("%d",&_);_;_--) { 18 scanf("%d%d%d",&n,&m,&d); 19 for(int i=1;i<=n;i++) { 20 G[i].clear(); 21 col[i]=0; 22 } 23 for(int i=0;i<m;i++) { 24 int x; 25 scanf("%d",&x); 26 col[x]=1; 27 } 28 for(int i=1;i<n;i++) { 29 int u,v; 30 scanf("%d%d",&u,&v); 31 G[u].push_back(v); 32 G[v].push_back(u); 33 } 34 dis[0]=-1; 35 dfs(1,0); 36 int maxx,s,t; 37 maxx=-1,s=-1; 38 for(int i=1;i<=n;i++) { 39 if(col[i]) { 40 if(dis[i]>maxx) { 41 maxx=dis[i]; 42 s=i; 43 } 44 } 45 } 46 dfs(s,0); 47 maxx=-1; 48 t=-1; 49 for(int i=1;i<=n;i++) { 50 if(col[i]) { 51 if(dis[i]>maxx) { 52 maxx=dis[i]; 53 t=i; 54 } 55 } 56 } 57 for(int i=1;i<=n;i++) col[i]=0; 58 for(int i=1;i<=n;i++) { 59 if(dis[i]<=d) col[i]=1; 60 } 61 dfs(t,0); 62 int ans=0; 63 for(int i=1;i<=n;i++) { 64 if(dis[i]<=d&&col[i]) ans++; 65 } 66 printf("%d ",ans); 67 } 68 }
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef double db; 5 typedef pair<int,int> pii; 6 typedef vector<int> vi; 7 #define de(x) cout << #x << "=" << x << endl 8 #define rep(i,a,b) for(int i=a;i<b;++i) 9 #define all(x) (x).begin(),(x).end() 10 #define sz(x) (int)(x).size() 11 #define mp make_pair 12 #define pb push_back 13 #define fi first 14 #define se second 15 16 const int N = 100005; 17 int n, m, d; 18 int h[N]; 19 vi g[N]; 20 int vis[N], dis[N]; 21 22 int bfs(int s, int f) { 23 queue<int> Q; 24 Q.push(s); 25 vis[s]++; 26 dis[s] = 0; 27 while (!Q.empty()) { 28 int u = Q.front(); Q.pop(); 29 for(int i = 0; i < sz(g[u]); i++) { 30 int v = g[u][i]; 31 if (vis[v] == f) { 32 vis[v]++; 33 Q.push(v); 34 dis[v] = dis[u] + 1; 35 } 36 } 37 } 38 int Max = -1, ans; 39 for (int i = 1; i <= n; i++) { 40 if (h[i]) { 41 if (Max < dis[i]) { 42 Max = dis[i]; 43 ans = i; 44 } 45 } 46 } 47 return ans; 48 } 49 50 void solve() { 51 52 scanf("%d%d%d", &n, &m, &d); 53 for (int i = 1; i <= n; i++) h[i] = 0, g[i].clear(), vis[i] = 0; 54 memset(h, 0, sizeof(h)); 55 while (m--) { 56 int x; scanf("%d", &x); 57 h[x] = 1; 58 } 59 for (int i = 1; i < n; i++) { 60 int u, v; scanf("%d%d", &u, &v); 61 g[u].pb(v); 62 g[v].pb(u); 63 } 64 int s = bfs(1, 0); 65 int t = bfs(s, 1); 66 for(int i = 1; i <= n; i++) h[i] = 0; 67 for(int i = 1; i <= n; i++) if (dis[i] <= d) h[i]++; 68 bfs(t, 2); 69 int ans = 0; 70 for (int i = 1; i <= n; i++) if (dis[i] <= d && h[i]) ans++; 71 printf("%d ", ans); 72 73 } 74 75 int main() { 76 int ti; 77 scanf("%d", &ti); 78 for (int i = 0; i < ti; i++) { 79 solve(); 80 } 81 return 0; 82 }
魔法扑克
分析可以发现花色是最主要的（算贪心？易证）。所以就可以找到出现花色最多的牌，但是不是这种花色的牌都满足，比如 2 3 8 9 10 显然最长合法的是8 9 10。因为2 和 3跟他们连不到一起。且 2 3长度为2，小于8 9 10长度为3。
还要处理 1的情况。当时傻逼了，以为1和13必须得同时出现。。。其实出现1就可以了。自闭。。。。改了就AC了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 5 int _; 6 vector<int> t[10]; 7 //A12 A6 A5 A10 A1 8 int main() { 9 //freopen("in.txt", "r", stdin); 10 //freopen("out.txt", "w", stdout); 11 map<char,int> mp; 12 mp['A']=1; 13 mp['B']=2; 14 mp['C']=3; 15 mp['D']=4; 16 for(scanf("%d",&_);_;_--) { 17 string s; 18 memset(t,0,sizeof(t)); 19 for(int i=0;i<5;i++) { 20 cin>>s; 21 int id=s[0]-'A'+1; 22 int num=0,len=s.length(); 23 for(int i=1;i<len;i++) { 24 num=num*10+s[i]-'0'; 25 } 26 t[id].push_back(num); 27 } 28 int ans=-1,maxx=-1; 29 for(int i=1;i<=4;i++) { 30 if(!t[i].size()) continue; 31 int flag=0,len=t[i].size(); 32 for(int j=0;j<len;j++) { 33 if(t[i][j]==1) { 34 flag=1; 35 break; 36 } 37 } 38 vector<int> tmp; 39 tmp=t[i]; 40 sort(tmp.begin(),tmp.end()); 41 maxx=-1; 42 for(int j=1;j<=len;j++) { 43 for(int k=0;k+j-1<len;k++) { 44 if(tmp[k+j-1]-tmp[k]<5) { 45 maxx=max(maxx,j); 46 break; 47 } 48 } 49 } 50 if(flag) { 51 for(int j=0;j<len;j++) { 52 if(t[i][j]==1) { 53 t[i][j]=14; 54 break; 55 } 56 } 57 tmp=t[i]; 58 sort(tmp.begin(),tmp.end()); 59 for(int j=1;j<=len;j++) { 60 for(int k=0;k+j-1<len;k++) { 61 if(tmp[k+j-1]-tmp[k]<5) { 62 maxx=max(maxx,j); 63 break; 64 } 65 } 66 } 67 } 68 ans=max(maxx,ans); 69 } 70 printf("%d ",5-ans); 71 } 72 }
第x个数、敲7、集合运算、最长单词、Distribution
暴力、模拟即可