树形动态规划 #include <iostream> #include<vector> #include<algorithm> using namespace std; using ll=long long; const int MAXN=2e5+5; vector<int>son[MAXN]; int w[MAXN]; ll dp[MAXN][2]; void dfs(int u){ dp[u][1]=w[u]; dp[u][0]=0; for(int v:son[u]){ dfs(v); dp[u][1]+=dp[v][0]; dp[u][0...

统计a[i]-i的数量，利用组合数计算谐距下标对数 #include <iostream> #include<vector> #include<unordered_map> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; vector<int>a(n); unordered_map<int,int>cnt; for(int i=0;i<n;i++){ cin>>a...

#include <iostream> #include<string> #include<unordered_map> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; unordered_map<string,int>count; int cnt=0; for(int i=0;i<n;i++){ string word; cin>>word; if(count[word]&...

#include <iostream> #include<string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin>>s; int n=s.size(); if(s[1]=='9'&&s[2]>='5'){ if(s[0]!='9')cout<<s[0]+1-'0'<<".0*10^"<<n-1; else cout<<&q...

#include <iostream> #include<string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int r=0,g=0,b=0; string s; cin>>s; for(char c:s){ if(c=='R')r++; if(c=='G')g++; if(c=='B')b++; } cout<<"("<<r<<","<<g&lt...

各个位相加为9的倍数可以被9整除，每个2可以增加2，每个3可以增加6 #include <iostream> #include<string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin>>t; while (t--) { int num[10] = {0}; int sum = 0; string s; cin >> s; for (char c:s) { int x=c-'0'; sum+=x; num[...

前缀和 #include <iostream> #include<vector> #include<string> using namespace std; int main() { string s; cin>>s; s=" "+s; vector<long long>prefix(s.size(),0); for(int i=1;i<s.size();i++){ int a; if(s[i]=='P')a=3; else if(s[i]=='p')a=2; else if(s[i]=='G')a=1; e...

模拟未知温度，计算寒潮天数 #include <iostream> #include<vector> using namespace std; const int INF=-999; const int MIN_T=-50; const int MAX_T=50; int maxcold(int n,int x,const vector<int>&arr){ vector<int>a(arr); if(a[0]==INF)a[0]=MAX_T; for(int i=1;i<n;i++){ if(a[i]==INF){ int cur...

sum为所有位数模3的和，cnt[i]为非0数位模3后为i的个数。1.小红操作时，如果非0数位只有1个，小红输；cnt[sum]!=0时，小红可以删除，反之必输。2.小紫操作时，cnt[1] == 0 && cnt[2] == 0 && cnt[0] == 0没有非零数位剩下 ⇒ 小紫无法操作 ⇒ 小红赢；cnt[1] == cnt[2] && cnt[0] > 0余1和余2的数位数量相等，且有余0的数位，这是一个对称局面，小红有必胜策略；其他情况小紫有必胜策略 #include <iostream> #include<s...

#include <iostream> #include<vector> #include<algorithm> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,q; cin>>n>>q; vector<int>a(n); for(int&x:a)cin>>x; sort(a.begin(),a.end()); while(q--){ long long l,r; cin>...

利用二维数组记录每个字母的位置，进而可得子链长度 #include <iostream> #include<string> #include<vector> #include<climits> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,k; string s; cin>>n>>k>>s; vector<vector<int>>a(26); for(int i...

统计每个连续段的长度 #include<iostream> #include<vector> #include<string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; string s; cin >> n >> k >> s; vector<int>len; int cnt = 1; for (int i = 1; i < n; i++) { if (s[i] ==...

#include <iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n; cin>>n; vector<char>ch; for(int i=0;i<n;i++){ ch.push_back('A'+i); } do{ for(int i=0;i<n;i++){ if(i>0)cout<<"+"; cout<<ch[i]; } cout<<&...

素数筛+前缀和 #include <iostream> #include<vector> using namespace std; const int MAX=1e6; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); vector<bool>isprime(MAX+1,true); isprime[0]=isprime[1]=false; for(int i=2;i*i<=MAX;i++){ if(isprime[i]){ for(int j=i*i;j<=MAX;j+=i)...