A。双指针如果定义好 l 和 r 的含义就变得很好写了。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn= 500000 + 100; LL color[maxn],cnt[maxn],a[maxn],ans[maxn]; int main() { LL n; scanf("%I64d",&n); for( LL i = 1;i <= n;i++ ){ scanf("%I64d",&a[i]); } LL l = 0,r = 1; while( l < n ){ while( r <= n && !( a[r] > 0 && cnt[ a[r] ] > 0) ){ r++; if( a[r-1] < 0 ) cnt[ -a[r-1] ]++; } ans[l] = r-l-1; l++; if( a[l] < 0 ){ cnt[ -a[l] ]--; } } for( LL i = 0;i < n;i++ ) printf("%I64d ",ans[i]); return 0; }B。签到
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn= 1000 + 10; LL cnt[5]; char str1[maxn],str2[maxn]; int main() { scanf("%s",str1); scanf("%s",str2); LL n = strlen( str1 ); for( LL i = 0;i < n;i++ ){ if( str1[i] == '#' ){ if( str2[i] == '#' ){ cnt[3]++; }else{ cnt[2]++; } }else{ if( str2[i] == '#' ){ cnt[1]++; }else{ cnt[0]++; } } } bool flag3 = cnt[3] == 0; bool flag2 = cnt[2] == 0; bool flag1 = cnt[1] == 0; if( flag3 ){ if( !(flag2||flag1) ){ printf("NO\n"); return 0; } } LL i = 0; for( ;i < cnt[1];i++ ){ str1[i] = '.'; str2[i] = '#'; } for( ;i < cnt[1] + cnt[3];i++ ){ str1[i] = '#'; str2[i] = '#'; } for( ;i < cnt[1] + cnt[3] + cnt[2];i++ ){ str1[i] = '#'; str2[i] = '.'; } for( ;i < n;i++ ){ str1[i] = '.'; str2[i] = '.'; } str1[n] = '\0'; str2[n] = '\0'; printf("YES\n"); printf("%s\n",str1); printf("%s\n",str2); return 0; }c。这题打个表发现走不了几步就没有能够新到达的点了。于是瞎写了一发居然过了。（感觉的重要性）
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 10000000 + 10; LL vis[maxn]; int main() { //freopen( "456.txt","w",stdout ); LL p,n; scanf("%I64d%I64d",&p,&n); vis[0] = 1; LL cnt = 1; LL h = min( p*2,n ); for( LL i = 1;i <= h;i++ ){ LL b = (i*(i+1)/2) % p; if( !vis[ b ] ){ vis[b] = 1; cnt++; } } printf("%I64d\n",cnt); return 0; }D。这题我一开使想找一个点，使其子树中包含所有红点（蓝点），而不包含任何蓝点（红点）。即dfs一遍整个树统计。
但是由于查询次数太多，复杂度爆炸了。所以就得上lca了，找到所有蓝点的lca，和所有红点的lca。若其中一个lca的子树不包含另一个颜色的任何点。就有可行解。（这题启发我找多个点的lca的方法和在树上判断一个点是否是另一个点祖先的方法）
#include<bits/stdc++.h> using namespace std; typedef int lint; typedef long long LL; const lint maxn = 200000 + 10; const lint maxm = 500000; lint ver[maxm],ne[maxm],he[maxn],tot; vector<lint> vex,vey; void init(){ memset( he,0,sizeof( he ) ); tot = 1; } void add( lint x,lint y ){ ver[++tot] = y; ne[tot] = he[x]; he[x] = tot; } struct lca{ lint de[maxn],anc[maxn][21]; queue<lint> que; void init(){ memset( anc,-1,sizeof( anc ) ); while( que.size() ) que.pop(); } void bfs( ){ que.push( 1 ); de[1] = 0; while( que.size() ){ lint x = que.front(); que.pop(); for( lint cure = he[x];cure;cure = ne[cure] ){ lint y = ver[cure]; if( y == anc[x][0] ) continue; que.push(y); de[y] = de[x] + 1; anc[y][0] = x; for( lint i = 1; (1 << i) <= de[y]; i++ ){ anc[y][i] = anc[ anc[y][i-1] ][i-1]; } } } } lint solve( lint x,lint y ){ if( x == y ) return x; if( de[x] < de[y] ) swap( x,y ); for( lint i = 18; i >= 0;i-- ){ lint an = anc[x][i]; if( an == -1 ) continue; if( de[an] >= de[y] ){ x = an; } } if( x == y ) return y; for( lint i = 18; i >= 0; i-- ){ if( anc[x][i] == -1 || anc[y][i] ==-1 ) continue; if( anc[x][i] != anc[y][i] ){ x = anc[x][i]; y = anc[y][i]; } } return anc[x][0]; } }g; bool solve( const vector<lint>& ve,const lint anc ){ for( lint i = 0;i < ve.size();i++ ){ if( g.solve( ve[i],anc ) == anc ){ return false; } } return true; } int main(){ lint n,x,y,num; scanf("%d",&n); init(); g.init(); for( lint i= 1;i <= n-1;i++ ){ scanf("%d%d",&x,&y); add( x,y ); add( y,x ); } g.bfs(); scanf("%d",&num); while( num-- ){ vex.clear(); vey.clear(); lint p,q; scanf("%d%d",&p,&q); for( lint i = 1;i <= p;i++ ){ scanf("%d",&x); vex.push_back( x ); } for( lint i = 1;i <= q;i++ ){ scanf("%d",&y); vey.push_back( y ); } lint ancx = vex[0]; for( lint i = 0; i < vex.size();i++ ){ x = vex[i]; ancx = g.solve( x,ancx ); } lint ancy = vey[0]; for( lint i = 0;i < vey.size();i++ ){ y = vey[i]; ancy = g.solve( y,ancy ); } LL anc = g.solve( ancx,ancy ); if( anc != ancx && anc != ancy ){ printf("YES\n"); continue; } bool flag = true; if( ancx ==anc ){ flag = solve( vex,ancy ); }else{ flag = solve( vey,ancx ); } if( flag ){ printf("YES\n"); }else{ printf("NO\n"); } } return 0; }F。排序优化枚举。注意写法，vector的second提供索引，所有值都去原数组中去找。下标改为从0开始。
#include <bits/stdc++.h> using namespace std; typedef int lint; typedef long long LL; typedef pair<lint,lint> pii; const lint maxn = 300000 + 10; lint a[maxn],h[maxn]; vector<pii> vea,veh; priority_queue<pii> que; int main() { lint n,ans = 0,ansx = 1,ansy = 2; scanf("%d",&n); for( lint i = 0;i < n;i++ ){ scanf("%d%d",&a[i],&h[i]); vea.push_back( pii( a[i],i ) ); veh.push_back( pii( h[i],i ) ); } sort( vea.begin(),vea.end() ); sort( veh.begin(),veh.end() ); lint p = 0; for( lint i = 0;i < vea.size();i++ ){ pii x = vea[i]; while( p < n && vea[i].first >= veh[p].first ){ pii y = veh[p]; que.push( pii( a[ y.second ],y.second ) ); p++; } if( !que.size() ) continue; pii y = que.top(); pii t; bool flag = true; if( y.second == x.second ){ flag = false; t = y; que.pop(); if( !que.size() ){ que.push( t ); continue; } y = que.top(); } lint re = y.first; if( re >= h[ x.second ] ) re += a[ x.second ]; if( re > ans ){ ans = re; ansx = x.second+1; ansy = y.second + 1; } } printf("%d\n",ans); printf("%d %d\n",ansx,ansy); return 0; }
E。贪心策略同活动安排问题。
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,LL> pii; typedef pair<pii,LL> piii; priority_queue<piii> que1,que2; vector<LL> ans; LL m; bool solve( ){ LL cur = m; while( cur >= 1 ){ while( que1.size() && que1.top().first.first >= cur ){ piii x = que1.top(); que1.pop(); que2.push( piii(pii ( -x.first.second,-x.first.first ),x.second) ); } if( que2.empty() ) return false; piii x = que2.top(); que2.pop(); ans.push_back( x.second ); if( -x.first.first > cur ) return false; //这块的判断很重要，容易漏写 cur = -x.first.first-1; } return true; } int main() { LL n,x,y; scanf("%I64d%I64d",&n,&m); for( LL i = 1;i <= n;i++ ){ scanf("%I64d%I64d",&x,&y); que1.push( piii(pii(y,x),i) ); } bool flag = solve(); if(!flag ){ printf("NO\n"); return 0; } printf("YES\n"); printf("%I64d\n",(LL)ans.size()); for( LL i = 0;i < ans.size();i++ ){ printf("%I64d ",ans[i]); } return 0; }I。一圈一圈走，使得最后重叠的面积最小。
#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { LL a,b; scanf("%I64d%I64d",&a,&b); LL le = a*a - b*b; LL c = a % b ; le += ( b - c )* c ; printf("%I64d",le / b); return 0; }J。贪心，注意对结构体lowerbound要小心，WA了几次才发现这个问题。
#include <bits/stdc++.h> #define pb push_back using namespace std; typedef long long LL; const LL inf = 0x3f3f3f3f3f3f3f3f; vector<LL> ve1,ve2; LL summ[500005]; int main() { LL n,x,y,z; vector<LL> ve; scanf("%I64d",&n); for( LL i = 0;i < n;i++ ){ scanf("%I64d%I64d%I64d",&x,&y,&z); ve.clear(); ve.push_back(x); ve.push_back(y); ve.push_back(z); sort( ve.begin(),ve.end() ); x = ve[0];y = ve[1];z = ve[2]; ve1.push_back( x+y ); ve2.push_back( x+y+z ); summ[i] = x+y; } sort( ve1.begin(),ve1.end() ); for( LL i = 0;i < n;i++ ){ LL sum = ve2[i]; LL cnt = upper_bound( ve1.begin(),ve1.end(),sum-2 ) - ve1.begin(); if( summ[i] <= sum - 2 ) cnt--; printf("%I64d ",cnt); } return 0; }K。向一个日本的黄名大佬要的代码。
这题需要倒着想，其实这一点我想到了。但是我没有想到可以根据目标直接从原字符串中直接抽离出子串。
这末做的道理就在于连续性，开头一旦确定了，后来就都确定了。这个东西好熟悉啊，拓扑序搜索的典范？
#include <bits/stdc++.h> using namespace std; typedef long long LL; string str; LL vis[10000]; bool solve(string s){ string tar; for( char c : s ){ for( char cc : str ){ if( c == cc ) tar += c; } } LL pos = 0; memset( vis,0,sizeof( vis ) ); LL len = str.length(); for( LL i = 0;i < len;i++ ){ if( str[i] == tar[pos] ){ pos++; vis[i] = 1; } } for( LL i = 0;i < len;i++ ){ if( vis[i] ) continue; if( str[i] == tar[pos] ){ pos++; vis[i] = 1; } } if( pos == len ) return true; return false; } int main() { cin >> str; cout << ( ( solve( "BGR" ) || solve( "BRG" ) || solve( "RBG" ) || solve( "RGB" ) || solve( "GBR" ) || solve( "GRB" ) ) ? "YES" : "NO"); return 0; }
