思路
打表模拟，签到题。
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <cstdio> 5 #include <map> 6 #include <set> 7 #include <vector> 8 #include <cstdlib> 9 #include <queue> 10 11 using namespace std; 12 13 char a[3][15]={{'Q','W','E','R','T','Y','U','I','O','P'},{'A','S','D','F','G','H','J','K','L','#'},{'Z','X','C','V','B','N','M','#','#','#','#'}}; 14 15 pair<int,int> ans; 16 17 void Find(string s){ 18 for(int i=0;i<3;i++){ 19 for(int j=0;j<10;j++){ 20 if(a[i][j]==s[0]){ 21 ans.first=i; 22 ans.second=j; 23 return; 24 } 25 } 26 } 27 } 28 29 int main(){ 30 int T; 31 cin>>T; 32 while(T--){ 33 string s,opt; 34 cin>>s>>opt; 35 Find(s); 36 if(opt=="Right"){ 37 if(ans.second<9&&a[ans.first][ans.second+1]!='#') cout<<a[ans.first][ans.second+1]<<endl; 38 else cout<<"No letter."<<endl; 39 } 40 else if(opt=="Left"){ 41 if(ans.second>=1&&a[ans.first][ans.second-1]!='#') cout<<a[ans.first][ans.second-1]<<endl; 42 else cout<<"No letter."<<endl; 43 } 44 } 45 return 0; 46 }
思路
排序的模拟……签到题
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <algorithm> 6 #include <string> 7 #include <map> 8 9 using namespace std; 10 11 const int maxn=1500; 12 13 struct node{ 14 int id,ac,time; 15 string name; 16 }stu[maxn]; 17 18 int flag[maxn][100],wa[maxn][100]; 19 20 inline int read(){ 21 int x=0,f=1;char ch=getchar(); 22 while(ch>'9'||ch<'0'){ 23 ch=getchar(); 24 } 25 while(ch>='0'&&ch<='9'){ 26 x=x*10+ch-'0'; 27 ch=getchar(); 28 } 29 return x*f; 30 } 31 32 int cmp(const node&a,const node&b){ 33 if(a.ac==b.ac){ 34 if(a.time==b.time){ 35 return a.id<b.id; 36 } 37 return a.time<b.time; 38 } 39 return a.ac>b.ac; 40 } 41 42 int main(){ 43 int n,m,k; 44 n=read();m=read();k=read(); 45 for(int i=1;i<=n;i++){ 46 string s;cin>>s; 47 stu[i].id=i;stu[i].name=s; 48 } 49 for(int i=0;i<m;i++){ 50 int a,b,c;string tem;a=read();b=read();c=read();cin>>tem; 51 if(tem[0]=='A'&&flag[b][c]==0){ 52 stu[b].time+=(a+wa[b][c]*20); 53 stu[b].ac++; 54 flag[b][c]=1; 55 } 56 else if(tem[0]=='W'&&flag[b][c]==0){ 57 wa[b][c]++; 58 } 59 } 60 sort(stu+1,stu+n+1,cmp); 61 for(int i=1;i<=n;i++){ 62 cout<<stu[i].name<<" "<<stu[i].ac<<" "<<stu[i].time<<endl; 63 } 64 return 0; 65 }
思路
做了40min搞出来的，由于膜法只能去掉一条边的权值，所以最优解是去掉当前最短路（dijkstra的时候）的最大边，所以分类讨论：
①当前状态没有使用膜法，所以有两种松弛方向：不使用膜法（普通最短路松弛1图），使用膜法（松弛2图），②当前状态使用过膜法，这时候只需要松弛2图就行。
为什么不能松弛同一张图？因为必须要保证只能去掉一条边，如果从同一张图松弛则不能满足。
1 #include <iostream> 2 #include <cstring> 3 #include <string> 4 #include <cstdio> 5 #include <map> 6 #include <set> 7 #include <vector> 8 #include <cstdlib> 9 #include <queue> 10 #include <functional> 11 12 using namespace std; 13 14 typedef pair<int,int> P; 15 16 const int maxn=10005; 17 const int inf=1000000000; 18 19 struct node{ 20 int v,t,pos,mx; 21 bool operator <(const node&a) const{ 22 return v>a.v; 23 } 24 }; 25 26 vector<P> G[maxn]; 27 28 int n,m,st,ed; 29 int d[2][maxn];//0表示1图，1表示2图 30 bool used[2][maxn]; 31 32 inline int read(){ 33 int x=0,f=1;char ch=getchar(); 34 while(ch>'9'||ch<'0'){ 35 ch=getchar(); 36 } 37 while(ch>='0'&&ch<='9'){ 38 x=x*10+ch-'0'; 39 ch=getchar(); 40 } 41 return x*f; 42 } 43 44 void init(){ 45 for(int i=0;i<maxn;i++){ 46 G[i].clear(); 47 d[0][i]=d[1][i]=inf; 48 used[0][i]=used[1][i]=0; 49 } 50 } 51 52 void dij(int s){ 53 d[0][s]=0; 54 priority_queue<node>q; 55 q.push((node){d[0][s],s,0,0}); 56 while(!q.empty()){ 57 int now=q.top().t; 58 int nowv=q.top().v; 59 int pos=q.top().pos; 60 int mxw=q.top().mx; 61 q.pop(); 62 if(used[pos][now]) continue; 63 used[pos][now]=1; 64 for(int i=0;i<G[now].size();i++){ 65 int v=G[now][i].first; 66 int w=G[now][i].second; 67 int tw=max(mxw,w);//这里一定要注意不能直接更新mxw，因为每条最短路的路径不同，最大边也不同 68 if(pos==0){ 69 if(d[0][v]>nowv+w){//普通最短路，松弛1图 70 d[0][v]=nowv+w; 71 q.push((node){d[0][v],v,0,tw}); 72 } 73 if(d[1][v]>nowv-tw+w){//使用膜法，松弛2图 74 d[1][v]=nowv-tw+w; 75 q.push((node){d[1][v],v,1,tw}); 76 } 77 } 78 else{ 79 if(d[1][v]>nowv+w){//使用过膜法，松弛2图 80 d[1][v]=nowv+w; 81 q.push((node){d[1][v],v,1,tw}); 82 } 83 } 84 } 85 } 86 } 87 88 int main(){ 89 int T; 90 T=read(); 91 while(T--){ 92 init(); 93 n=read();m=read();st=read();ed=read(); 94 for(int i=0;i<m;i++){ 95 int s,t,w;s=read();t=read();w=read(); 96 G[s].push_back(P(t,w)); 97 G[t].push_back(P(s,w)); 98 } 99 dij(st); 100 printf("%d ",d[1][ed]); 101 } 102 return 0; 103 }
思路
这道题赛场上看着很吓人，赛后仔细思考发现……必胜态只有一种情况：a和b邻接，其他都为必败态。原因是取消边的操作是后手。
假设a点可以成功到达b点，那么在上一步，a点位于b点的邻接边的端点，那么ab这条边一定会被后手操作取消。所以只有当ab邻接时才会赢。
1 #include <iostream> 2 #include <cstring> 3 4 using namespace std; 5 6 const int maxn=30; 7 8 int mp[maxn][maxn]; 9 10 int n,m,a,b; 11 12 int main(){ 13 int T; 14 cin>>T; 15 while(T--){ 16 cin>>n>>m>>a>>b; 17 memset(mp,-1,sizeof(mp)); 18 for(int i=0;i<m;i++){ 19 int s,t;cin>>s>>t; 20 mp[s][t]=mp[t][s]=1; 21 } 22 if(mp[a][b]==1) cout<<"chhappy"<<endl; 23 else cout<<"chsad"<<endl; 24 } 25 return 0; 26 }
思路
由于必须要进行不同位置上的翻转，排序比较后记录不同次数，如果==2或两个字符串元素相同且某个元素数量>2时有解，所以……xjb搞
1 #include <iostream> 2 #include <set> 3 #include <string> 4 #include <algorithm> 5 #include <string> 6 #include <set> 7 8 using namespace std; 9 10 set<char> rt; 11 12 int main(){ 13 ios_base::sync_with_stdio(false); 14 cin.tie(0); 15 int T; 16 cin>>T; 17 while(T--){ 18 string s1,s2,s3,s4; 19 rt.clear(); 20 cin>>s1>>s2; 21 s3=s1,s4=s2; 22 sort(s3.begin(),s3.end()); 23 sort(s4.begin(),s4.end()); 24 int cou=0;bool flag=false; 25 if(s3==s4){ 26 for(int i=0;i<s1.length();i++){ 27 if(s1[i]!=s2[i]){ 28 flag=true; 29 cou++; 30 if(cou>2){ 31 cout<<"NO"<<endl; 32 break; 33 } 34 } 35 rt.insert(s1[i]); 36 } 37 } 38 else{ 39 cout<<"NO"<<endl; 40 continue; 41 } 42 if(cou<=2){ 43 if(cou==2||(!flag&&rt.size()!=s1.length())){ 44 cout<<"YES"<<endl; 45 } 46 else cout<<"NO"<<endl; 47 } 48 } 49 return 0; 50 }
思路
推公式……
1 #include<cstring> 2 #include<cmath> 3 #include<cstdio> 4 #include<iostream> 5 using namespace std; 6 #define g 9.8 7 8 int main(){ 9 int T; 10 scanf("%d",&T); 11 while(T--){ 12 double v,a; 13 scanf("%lf%lf",&v,&a); 14 printf("%.2f ",(v*v/9.8)*(a/9.8+sqrt(1+a*a/(g*g)))); 15 } 16 return 0; 17 }