首页 > 代码库 > Codeforces Round #272 (Div. 2) ABCDE
Codeforces Round #272 (Div. 2) ABCDE
A. Dreamoon and Stairs
题解:
首先写出尽可能2多的步数,然后判断能否%m,不能就加上最小的数使其能%m就行了
代码:
#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int N=1e5+10;const int M=1e3+10;const int mod=1e9+7;const int INF=1e9+10;int n,m;int main(){ int n,m; cin>>n>>m; if(n<m) cout<<-1<<endl; else{ int ans=n/2+(n%2==0?0:1); if(ans%m==0) cout<<ans<<endl; else{ for(int i=1;i<m;i++){ if((ans+i)%m==0){ cout<<ans+i<<endl; break; } } } }}
B.Dreamoon and WiFi
题解:
简单dp,递推搜索一下就行了
代码:
#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int N=1e5+10;const int M=1e3+10;const int mod=1e9+7;const int INF=1e9+10;string s1,s2;int cnt1,cnt,len;void DP(int pos,int c){ if(pos==len){ if(c==cnt1) cnt++; return; } if(s2[pos]==‘+‘) DP(pos+1,c+1); if(s2[pos]==‘-‘) DP(pos+1,c-1); if(s2[pos]==‘?‘){ DP(pos+1,c-1); DP(pos+1,c+1); }}int main(){ cin>>s1>>s2; cnt1=0,cnt=0; len=s1.length(); for(int i=0;i<len;i++) if(s1[i]==‘+‘) cnt1++;else cnt1--; int sum=1; for(int i=0;i<len;i++) if(s2[i]==‘?‘) sum*=2; DP(0,0); cout<<setprecision(15)<<(double)cnt/(double)sum<<endl; return 0;}
C.Dreamoon and Sums
题解:
注意到x/b=x/b*b+x%b就行。然后注意每个计算位置都要计算取mod.....
代码:
#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int N=1e5+10;const int M=1e3+10;const LL mod=1000000007;const int INF=1e9+10;LL a,b;int main(){ cin>>a>>b; LL k=((1LL+a)*a/2%mod*b%mod+a)%mod; LL sum=0; for(LL i=1;i<b;i++){ sum+=i*k; sum%=mod; } cout<<sum<<endl;}
D. Dreamoon and Sets
题解:
规律题,不多说
代码:
#include <iostream>using namespace std;int main(){ int n,k; cin>>k>>n; cout<<(6*k-1)*n<<endl; for(int i=0;i<k;i++)cout<<n*(6*i+1)<<" "<<n*(6*i+2)<<" "<<n*(6*i+3)<<" "<<n*(6*i+5)<<endl;}
E. Dreamoon and Strings
题解:
暴力处理每个位置,从后面到前面的第一个模板的位置,然后dp处理
参考博客http://www.cnblogs.com/qscqesze/p/5794709.html
代码:
//Coding by qscqesze#include<bits/stdc++.h>using namespace std;const int maxn = 2005;char s1[maxn],s2[maxn];int dp[maxn][maxn];int len1,len2;int solve(int x){ if(x<len2)return maxn; int a=x,b=len2,tmp=0; while(a&&b) { if(s1[a]==s2[b])a--,b--; else tmp++,a--; } if(b==0)return tmp; else return maxn;}int main(){ scanf("%s%s",s1+1,s2+1); len1 = strlen(s1+1); len2 = strlen(s2+1); for(int i=0;i<=len1;i++) for(int j=0;j<=len1;j++) if(j>i)dp[i][j]=-3000; for(int i=1;i<=len1;i++) { int x=solve(i); for(int k=0;k<=len1;k++) dp[i][k]=max(dp[i][k],dp[i-1][k]); for(int k=0;k<=len1;k++)if(x<=k) dp[i][k]=max(dp[i][k],dp[i-x-len2][k-x]+1); } for(int i=0;i<=len1;i++) printf("%d ",dp[len1][i]); printf("\n");}
Codeforces Round #272 (Div. 2) ABCDE
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。