Educational Codeforces Round 107 (Rated for Div. 2)
A - Review Site思路：数1和3的个数
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=250+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
void init(){
}
void solve(){
int n;cin>>n;
int ans=0;
for(int i=0,x;i<n;++i){
cin>>x;
if(x==1||x==3)ans++;
}cout<<ans<<'\n';
return;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
init();
while(t--){
solve();
}
return 0;
}
View Code
思路1：令gcd（x，y）=pow（10，c-1），x和y分别一直乘3和7，直到达到a和b位数
思路2：x=pow（10，a-1）+pow（10，c-1），y=pow（10，b-1）
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=250+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
void init(){
}
void solve(){
int a,b,c;cin>>a>>b>>c;
int x,y,z;
z=pow(10,c-1);
x=y=z;
while(x<pow(10,a-1))x*=3;
while(y<pow(10,b-1))y*=7;
cout<<x<<' '<<y<<'\n';
return;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
init();
while(t--){
solve();
}
return 0;
}
View Code
思路：由于数的范围很小，维护每个数的最小位置即可，更新时枚举每个数，若位置在其前面则后移
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=250+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
void init(){
}
void solve(){
int n,q;cin>>n>>q;
vector<int>c(55,n+5);
for(int i=1,x;i<=n;++i){
cin>>x;
c[x]=min(c[x],i);
}
for(int i=0,x;i<q;++i){
cin>>x;
cout<<c[x]<<' ';
for(int j=1;j<=50;++j){
if(c[j]<c[x])c[j]++;
}
c[x]=1;
}
return;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
init();
while(t--){
solve();
}
return 0;
}
View Code
思路：可以看出规律 a ab ac ad... b bc bd...
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=250+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
void init(){
}
void solve(){
int n,k;cin>>n>>k;
vector<int>f(30,0);
string s;
for(int i=0;i<k;++i){
s.push_back('a'+i);
for(int j=i+1;j<k;++j){
s.push_back('a'+i);
s.push_back('a'+j);
}
}
string ans;
while(ans.size()<n){
ans+=s;
}
for(int i=0;i<n;++i)cout<<ans[i];
return;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
init();
while(t--){
solve();
}
return 0;
}
View Code
思路：将求每个方案的数量和的问题，转化为求每个多骨牌的贡献；由于染蓝色和染红色的多骨牌不同，可以分别求两种牌的贡献；
对于一行\一列中连续的k个'o'的多骨牌摆放方案数其实一样，那么预处理出f[i]，表示连续i个'o'的所有摆放方案能放的多骨牌数；
对于每个连续的'o'串，贡献为f[i]*2all-i
f[i]的状态转移：
当第i个为蓝色，没有贡献，f[i]+=f[i-1]
当第i个为红色：第i-1个为蓝色时，第i个和第i-1个无法放多骨牌，f[i]+=f[i-2]
第i-1个为红色时，给前i-2个都新增一个方案，f[i]+=f[i-2]；第i个和第i-1个放一个多骨牌，前i-2个有2i-2个方案数，f[i]+=2i-2
即f[i]=f[i-1]+2f[i-2]+2i-2
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
void init(){
}
void solve(){
int n,m;cin>>n>>m;
vector<vector<char>>g(n+1,vector<char>(m+1));
int all=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)cin>>g[i][j],all+=(g[i][j]=='o');
int ans=0;
vector<int>fact(N),f(N);
fact[0]=1;
for(int i=1;i<=all;++i)fact[i]=fact[i-1]*2%mod;
f[0]=f[1]=0;
for(int i=2;i<=max(n,m);++i)f[i]=((f[i-1]+2*f[i-2])%mod+fact[i-2])%mod;
for(int i=1;i<=n;++i)
for(int j=1,k;j<=m;++j){
k=j;
while(j<=m&&g[i][j]=='o')j++;
ans=(ans+f[j-k]*fact[all-j+k]%mod)%mod;
}
for(int j=1;j<=m;++j)
for(int i=1;i<=n;++i){
int k=i;
while(i<=n&&g[i][j]=='o')i++;
ans=(ans+f[i-k]*fact[all-i+k]%mod)%mod;
}
cout<<ans;
return;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
init();
while(t--){
solve();
}
return 0;
}
View Code
标签：Educational,Rated,const,int,double,typedef,long,Codeforces,define From： https://www.cnblogs.com/bible-/p/17635392.html