D: Substring Characters
对于一个字符串s ，求所有不同的最短连续子串的数量，要求不能是s本身并且子串的不同字符的数量与s的不同字符的数量相同。
题意比较绕，最短的含义指的是删除某个子串t的前缀或后缀后，就无法保证不同字符的数量与s相同了。比如10411，可以删除后缀11，变成104。
双指针，队友写的
#include <bits/stdc++.h> using namespace std; char str[300]; map<char, bool>mp; map<char, int>mpp; map<string, bool> mppp; void solve() { mp.clear(); mpp.clear(); mppp.clear(); int len = strlen(str); int sum = 0; for(int i = 0; i < len; i++) { if(mp[str[i]] == 0) sum++; mp[str[i]] = 1; } int l = 0, r = 0, ans = 0, tmp = 0; for(int i = 0; i < len; i++) { while(r < len) { if(mpp[str[r]] == 0) tmp++; mpp[str[r]]++; r++; if(tmp == sum) { while(tmp == sum) { if(mpp[str[i]] == 1) tmp--; mpp[str[i]]--; i++; } i--; string s = ""; for(int j = i; j < r; j++) { s += str[j]; } if(i == 0 && r == len) { puts("0"); return ; } else if(mppp[s] == 0) { mppp[s] = 1; ans++; } if(r == len) { cout << ans << endl; return ; } break; } } if(r == len) { cout << ans << endl; return ; } } } int main() { while(~scanf("%s", str)) { solve(); } return 0; }
E: Curve Speed
给出r , s求v
int main() { double a,res; while(cin>>a>>res){ double ans=sqrt(a*(res+0.16)/0.067); printf("%.d\n",(int)(ans+0.5)); } return 0; }
F: Agamemnon’s Odyssey
给定一棵 N 个点的带边权树，可以任选一点作为起点，每条边最多经过 k 次，但只有在首次经过时才会贡献大小等于边权的价值，求价值和最大的一条路径。
当k = = 1时，答案是树的直径；
当k > 1时，答案是所有边权之和
const int maxn=2e5+100; ll n,k,ans; vector<PLL>g[maxn]; ll dfs(int u,int fa){ ll dist=0ll,d1=0ll,d2=0ll; for(auto t:g[u]){ int j=t.first,w=t.second; if(j==fa) continue; ll d=dfs(j,u)+w; dist=max(dist,d); if(d>=d1) d2=d1,d1=d; else if(d>d2) d2=d; } ans=max(ans,d1+d2); return dist; } int main() { n=read,k=read; rep(i,1,n-1){ int u=read,v=read,w=read; if(k>1) ans+=w; else g[u].push_back({v,w}),g[v].push_back({u,w}); } if(k==1) dfs(1,-1); printf("%lld\n",ans); return 0; }
H: Digital Speedometer
模拟
int main() { double tf,tr; cin>>tf>>tr; double s; double las=100000000; while(cin>>s){ double t=floor(s); if(s==0) las=0; else if(s>0&&s<1) las=1; else if(s>=t&&s<t+tf) las=floor(s); else if(s>t+tr&&s<t+1) las=ceil(s); else if(s>=t+tf&&s<=t+tr){ if(s<las) las=ceil(s); else las=floor(s); } printf("%.0f\n",las); } return 0; }
K: ICPC Record Matching
模拟。
const int maxn=2e5+100; string cul(string s){ string res=""; for(int i=0;s[i];i++){ if(s[i]>='A'&&s[i]<='Z'){ int t=s[i]-'A'; res+=(t+'a'); } else res+=s[i]; } return res; } struct node{ string first,last,email; }; bool cmp(node a,node b){ return cul(a.email)<cul(b.email); } vector<node>g[2]; set<PSS>s_name[2]; set<string>s_email[2]; vector<node>ans[2]; int main() { string str; while(getline(cin,str)){ if(str.size()==0) break; //cout<<str<<endl; stringstream ss; ss<<str; string a,b,c; ss>>a>>b>>c; g[0].push_back({a,b,c}); s_name[0].insert({cul(a),cul(b)}); s_email[0].insert(cul(c)); } //puts("*****"); while(getline(cin,str)){ //cout<<str<<endl; stringstream ss; ss<<str; string a,b,c; ss>>a>>b>>c; g[1].push_back({a,b,c}); s_name[1].insert({cul(a),cul(b)}); s_email[1].insert(cul(c)); } bool flag=1; for(int k=0;k<2;k++){ for(auto t:g[k]){ string a=cul(t.first),b=cul(t.last),c=cul(t.email); PSS ab={a,b}; int ant=1-k; if(!s_name[ant].count(ab)&&!s_email[ant].count(c)){ ans[k].push_back(t); flag=0; } } } if(flag) puts("No mismatches."); else{ for(int k=0;k<2;k++){ sort(ans[k].begin(),ans[k].end(),cmp); for(auto t:ans[k]){ if(k==0) cout<<"I "; else cout<<"O "; cout<<t.email<<" "<<t.last<<" "<<t.first<<"\n"; } } } return 0; }
