首页 > 代码库 > Codeforces Round #271 (Div. 2)
Codeforces Round #271 (Div. 2)
A题:因为数据量太小,所以直接暴力替换就好。。。。
#include <iostream> #include <algorithm> #include <string> #include <map> #include <vector> #include <string.h> using namespace std; typedef long long ll; int arr[100010]; int cnt[100010]; int col[100010]; int n,a,b; char c; string s = "qwertyuiopasdfghjkl;zxcvbnm,./"; int main() { while(cin>>c) { string input; cin>>input; if(c=='L') { string output=""; for(int i=0;i<input.length();i++) { for(int j=0;j<s.length();j++) { if(input[i]==s[j]) { output+=s[j+1]; break; } } } cout<<output<<endl; } else { string output=""; for(int i=0;i<input.length();i++) { for(int j=0;j<s.length();j++) { if(input[i]==s[j]) { output+=s[j-1]; break; } } } cout<<output<<endl; } } return 0; }
B题:数据只有100000,故可以直接用一个map记录每个点所在的区间标识。
#include <iostream> #include <algorithm> #include <string> #include <map> #include <vector> #include <string.h> using namespace std; typedef long long ll; int arr[100010]; int cnt[100010]; int col[100010]; int n,a,b; char c; string s = "qwertyuiopasdfghjkl;zxcvbnm,./"; int main() { while(cin>>n) { int all = 0; map<int,int> m; for(int i=1;i<=n;i++) { cin>>arr[i]; for(int j=all+1;j<=all+arr[i];j++) m[j]=i; all+=arr[i]; } int k; cin>>k; for(int i=0;i<k;i++) { int q; cin>>q; cout<<m[q]<<endl; } } return 0; }
C题:直接暴力枚举旋转的可能性,因为每个点最多转3次,最后判断是不是正方形就行。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> const int inf=9999999; using namespace std; struct node { int x; int y; }p[5][5],home[5]; long long d[8]; long long dis(node a,node b)//距离的平方 { return (long long)(a.x-b.x)*(a.x-b.x)+(long long)(a.y-b.y)*(a.y-b.y); } void solve() { int ans=inf; for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { for(int k=0;k<4;k++) { for(int l=0;l<4;l++) { d[0]=dis(p[i][0],p[j][1]);//四边距离的平方 d[1]=dis(p[j][1],p[k][2]); d[2]=dis(p[k][2],p[l][3]); d[3]=dis(p[l][3],p[i][0]); d[4]=dis(p[i][0],p[k][2]);//对角线的平方 d[5]=dis(p[j][1],p[l][3]); sort(d,d+6); if(d[0]==0) continue; else if(d[0]==d[1]&&d[1]==d[2]&&d[2]==d[3]&&2*d[3]==d[4]&&d[4]==d[5])//判断是否为正方形 { ans=min(ans,i+j+k+l); } } } } } if(ans!=inf) printf("%d\n",ans); else printf("-1\n"); } int main() { int t; scanf("%d",&t); while(t--) { for(int i=0;i<4;i++) { scanf("%d%d",&p[0][i].x,&p[0][i].y); scanf("%d%d",&home[i].x,&home[i].y); int x=p[0][i].x-home[i].x; int y=p[0][i].y-home[i].y; p[1][i].x=home[i].x-y;//逆时针旋转90度 p[1][i].y=home[i].y+x; p[2][i].x=home[i].x-x; p[2][i].y=home[i].y-y; p[3][i].x=home[i].x+y; p[3][i].y=home[i].y-x; } solve(); } return 0; }
D题:用dp[i][0]表示第i位不是W,dp[i][1]表示第i位是W,这样转移方程就很容易出来了,具体见代码,记得dp[0]时的初始化
#include <iostream> #include <algorithm> #include <string> #include <map> #include <vector> #include <string.h> using namespace std; typedef long long ll; ll dp[100010][2]; ll sum[100010]; int cnt[100010]; int col[100010]; int n,a,b,t,k; const int mod = 1e9+7; char c; string s = "qwertyuiopasdfghjkl;zxcvbnm,./"; int main() { while(cin>>t>>k) { memset(dp,0,sizeof(dp)); dp[0][0]=1; dp[0][1]=0; for(int i=1;i<=100000;i++) { dp[i][0] = (dp[i][0]+dp[i-1][0]+dp[i-1][1])%mod; if(i-k>=0) { dp[i][1] = (dp[i][1]+dp[i-k][0]+dp[i-k][1])%mod; } } sum[0] = 0; for(int i=1;i<=100000;i++) sum[i] = (sum[i-1]+dp[i][0]+dp[i][1])%mod; while(t--) { int a,b; cin>>a>>b; ll ans = sum[b]-sum[a-1]; if(ans<0) ans+=mod; cout<<ans<<endl; } } return 0; }
Codeforces Round #271 (Div. 2)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。