比赛链接
A.把数存下来然后算一下
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int main() { ios::sync_with_stdio(false); vector<pair<int,int> >v; for(int i=1;i<=9;i++){ int j=i; int k=1; while(j<=10000){ v.pb({j,k}); j=j*10+i; k++; } } int t; for(cin>>t;t;t--){ int x; cin>>x; int ans=0; for(auto k:v){ ans+=k.se; if(k.fi==x){ break; } } cout<<ans<<'\n'; } return 0; }B.找第一个1和最后一个1中间多少个0。比赛的时候写麻烦了。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int t,n,a[N]; int main() { ios::sync_with_stdio(false); for(cin>>t;t;t--){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; int L=-1; for(int i=1;i<=n;i++){ if(a[i]==1) { L = i; break; } } if(L==-1)cout<<0<<'\n'; else{ while(L+1<=n&&a[L+1]==1)L++; if(L==n)cout<<0<<'\n'; else{ int R=-1; for(int i=n;i>=1;i--){ if(a[i]==1){ R=i; break; } } int ans=0; for(int i=L;i<=R;i++)ans+=!a[i]; cout<<ans<<'\n'; } } } return 0; }C.找到一个值最大的数且这个数的两边至少有一个小于最大值。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 3e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int t,n,a[N]; int main() { ios::sync_with_stdio(false); for(cin>>t;t;t--){ cin>>n; int x=0; for(int i=1;i<=n;i++)cin>>a[i],x=max(x,a[i]); int ans=-1; for(int i=1;i<=n;i++){ if(a[i]==x&&(i>1&&a[i]>a[i-1] || i+1<=n&&a[i]>a[i+1])){ ans=i; } } cout<<ans<<'\n'; } return 0; }D.按值排序之后，如果所有数相等肯定无解。 否则全跟第一个数练，跟第一个数相等的跟最后一个连即可。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int t,n,a[N],f[N]; int main() { ios::sync_with_stdio(false); for(cin>>t;t;t--){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i],f[i]=i; sort(f+1,f+1+n,[](int x,int y){return a[x]<a[y];}); if(a[f[1]]==a[f[n]])cout<<"NO\n"; else{ cout<<"YES\n"; for(int i=2;i<=n;i++){ if(a[f[i]]!=a[f[1]]){ cout<<f[i]<<' '<<f[1]<<'\n'; }else{ cout<<f[i]<<' '<<f[n]<<'\n'; } } } } return 0; }E.从n个人中选n/2个放第一批方案是 ( n / 2 n ) (^n_{n/2}) (n/2n)，然后n/2个人组成的圆环有 ( n / 2 − 1 ) ! (n/2-1)! (n/2−1)!个。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; LL getpc(LL m, LL n){ LL ans = 1; for (LL k = 1; k <= n; k++){ ans = (ans * (m - n + k)) / k; } return ans; } int n; int main() { ios::sync_with_stdio(false); cin>>n;LL z=1; for(int i=1;i<=n/2-1;i++){ z*=i; } cout<<getpc(n,n/2)*z*z/2; return 0; }F.直接dp i j d表示i行选j个数 和%k=d的最大sum。 注意数组的初始化。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int n,m,k,a[77][77]; int dp[77][77][77],res[77][77],ans[77][77]; int main() { ios::sync_with_stdio(false); cin>>n>>m>>k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++)cin>>a[i][j]; } int z=m/2; memset(res,-1,sizeof res); for(int j=1;j<=n;j++){ memset(dp,-1,sizeof dp); dp[0][0][0]=0; for(int i=1;i<=m;i++){ for(int d=0;d<=z;d++){ for(int q=0;q<k;q++){ if(d+1<=z&&~dp[i-1][d][q])dp[i][d+1][(q+a[j][i])%k]=max(dp[i-1][d][q]+a[j][i],dp[i][d+1][(q+a[j][i])%k]); if(~dp[i-1][d][q])dp[i][d][q]=max(dp[i][d][q],dp[i-1][d][q]); } for(int q=0;q<k;q++){ res[j][q]=max(res[j][q],dp[i][d][q]); assert(res[j][q]==-1||res[j][q]%k==q); //cout<<j<<' '<<q<<' '<<res[j][q]<<' '<<res[j][q]%k<<endl; } } } } memset(ans,-1,sizeof ans); ans[0][0]=0; for(int i=1;i<=n;i++){ for(int j=0;j<k;j++){ for(int q=0;q<k;q++){ if(~ans[i-1][j] &&~res[i][q])ans[i][(q+j)%k]=max(ans[i][(q+j)%k],ans[i-1][j]+res[i][q]); } for(int q=0;q<k;q++){ if(~ans[i-1][q])ans[i][q]=max(ans[i][q],ans[i-1][q]); } } } cout<<ans[n][0]<<'\n'; return 0; }G.跑n次dij，然后枚举删哪个边即可。 注意最短路可以不经过删的边。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e3 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int n,m,k; vector<pair<int,int>>v[N]; int vis[N]; LL res[N]; void gao(int x,int sum,LL *dis){ for(int i=1;i<=sum;i++)vis[i]=0,dis[i]=1e18; dis[x]=0; priority_queue<pair<LL,int>>q; q.push({0,x}); while(!q.empty()){ auto x=q.top(); q.pop(); if(vis[x.se])continue; vis[x.se]=1; for(auto k:v[x.se]){ if(dis[k.fi]>dis[x.se]+k.se){ dis[k.fi]=dis[x.se]+k.se; q.push({-dis[k.fi],k.fi}); } } } } LL dis[N][N],di[N][N]; int L[N],R[N]; struct uzi{ int s,t,w; }; vector<uzi>G; int main() { ios::sync_with_stdio(false); cin>>n>>m>>k; for(int i=1;i<=m;i++){ int s,t,w; cin>>s>>t>>w; v[s].emplace_back(t,w); v[t].emplace_back(s,w); G.pb({s,t,w}); } for(int i=1;i<=k;i++) { cin >> L[i] >> R[i]; if (L[i] == R[i]) continue; gao(L[i], n, res); for(int j=1;j<=n;j++)dis[i][j]=res[j]; gao(R[i], n, res); for(int j=1;j<=n;j++)di[i][j]=res[j]; } LL ans=LLONG_MAX; for(auto t:G){ LL res=0; for(int i=1;i<=k;i++){ res+=min({dis[i][t.s] + di[i][t.t], dis[i][t.t] + di[i][t.s],dis[i][R[i]]}); } ans=min(ans,res); } cout<<ans<<'\n'; return 0; }