2018-03-24201省赛选拔赛第一场

加密

水题 ： 注意 ‘ J ’

#include<bits/stdc++.h>
using namespace std;
int a[100];
char hang[1000];
char lei[1000];
int main()
{
    hang[1]='A';
    hang[2]='D';
    hang[3]='F';
    hang[4]='G';
    hang[5]='X';
    lei[1]='A';
    lei[2]='D';
    lei[3]='F';
    lei[4]='G';
    lei[5]='X';
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
                char c;
        cin>>c;
        if(c=='j'){
            
            a['i'-'a']=100*i+j;
            a[c-'a']=100*i+j;
        }
            a[c-'a']=100*i+j;
            //cout<<a[c-'a']<<endl;
        }
    }
   // cout<<"df"<<endl;
    string s;
    cin>>s;
    cout<<hang[a[s[0]-'a']/100]<<lei[a[s[0]-'a']%100];
    for(int i=1;i<s.size();i++){
        cout<<" "<<hang[a[s[i]-'a']/100]<<lei[a[s[i]-'a']%100];
    }
    cout<<endl;
    return 0;
}

带你去看星星~

以为是一道规律题 4*n-1
其实 是求 互质点对 个数

欧拉函数+线性筛

n的大小 达到 10^10也可以做 ，自己去看 杜教筛

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100005
int n,m,k;
int a[N];
const int MAXN = 3e6+5;
long long f[MAXN];
void SumPhiTable(int n)
{
    f[1] = 1;
    for(int i=2; i<n; ++i)
    {
        if(!f[i])
        {
            for(int j=i; j<n; j+=i)
            {
                if(!f[j]) f[j] = j;
                f[j] = f[j]/i * (i-1);
            }
        }
        f[i] += f[i-1];
    }
}

int main()
{

    SumPhiTable(1000000);

    int n;
    cin>>n;
    if(n==2){
            cout<<3<<endl;
        //return 3;
    }else if(n==3){
            cout<<5<<endl;
    }else {
            cout<<f[n-1]*2+1<<endl;
    }
    return 0;
}

玩个小游戏

抖机灵水题， 如果A 可以画，画中心就行了，自己想为什么

#include<bits/stdc++.h>
using namespace std;
int a[100];
char hang[1000];
char lei[1000];
int main()
{

    int n;

    int a,b,c;
    cin>>a>>b>>c;
    c=2*c;
    if(a<c||b<c){
        cout<<"The second one is winner.\n";
    }else{

          cout<<"The first one is winner.\n";

    }
    return 0;
}

智者的试炼

因为可选的珍珠只有15个 ，随便暴力 或 dfs 即可

#include<bits/stdc++.h>
using namespace std;
int a[100];
char hang[1000];
char lei[1000];
typedef long long ll;
ll ans=0;
ll zhi=0;
ll ff[50];
void dfs(int n,ll a){
if(n>=15){
    return;
}
else{
if(a+ff[n]<=zhi)
{
    ans=max(ans,a+ff[n]);
    dfs(n+1,a+ff[n]); // 拿
}
    dfs(n+1,a);//不拿
}
}
int main()
{
// 2147483648
    int f[50];//45
    f[0]=1;
    f[1]=1;
    ll t=1;
    int cn=0;
    for(int i=2;i<46;i++){
        f[i]=f[i-1]+f[i-2];
      //  cout<<f[i]<<endl;
      if(f[i]%2==0){ ff[cn++]=f[i];
      //cout<<f[i]<<endl;

      }
    }
    //cout<<cn<<endl;
    int vv;
    cin>>zhi;
    dfs(0,0);
    cout<<ans<<endl;
    return 0;
}

疯狂植物大战僵尸

树状数组 区间更新 单点查询

差分数组 都可以，差分貌似简单 一些

数据输入比较大 要用 scanf 不然会超时

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
int n,k,m;
int a[N];
int c[N];
void add(int i,int x){
while(i<=n){
    c[i]+=x;
    i+=(i&(-i));
}
}
int sum(int i){
    int s=0;
while(i>0){
    s+=c[i];
    i-=(i&(-i));
}
return s;
}
int main()
{
  while(cin>>n>>m>>k){
        int x,y;x=y=0;
    for(int i=1;i<=n;i++){

        cin>>x;
        add(i,x-y);y=x;
    }
    for(int i=0;i<m;i++){
        cin>>x>>y;
        add(x,-1);add(y+1,1);
    }
    int cn=0;
    for(int i=1;i<=n;i++){
        int t=sum(i);
        //cout<<t<<endl;
        if(t<=k){
            if(cn==0)cout<<i;else cout<<" "<<i;
            cn++;
        }
    }
    if(cn==0){
        cout<<"Game Over";
    }
    cout<<endl;
  }
    return 0;
}

佛性AC

开始以为是 记忆化搜索 超时了
改成dp 就过了。 根据题意 这道题只跟 2、5因子个数有关，er 数组 wu数组 记录 每个位置2，5因子的个数。
dp[x][y] 表示到达（x,y）位置最小的2因子个数
dp1[x][y] 表示到达（x,y）位置最小的5因子个数
转移方程 dp[x][y]=min(dp[x-1][y],dp[x][y-1])+er[x][y]
因为 （x,y）位置的 2的个数 只能由 上面个 左边的位置 得来

同理 在求出 dp1[x][y]

最后的结果 一定是 min(dp[n][n],dp1[n][n])
为什么那?自己想

#include<bits/stdc++.h>
using namespace std;
#define N 1001
typedef long long ll;
#define INF 0x3f3f3f3f
int er[N][N];
int wu[N][N];
int n;
int dp[N][N];
int dp1[N][N];
int main()
{
    //cin>>n;
    scanf("%d",&n);
    int t,tt;
    memset(dp,0,sizeof(dp));
    memset(dp1,0,sizeof(dp1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){

            int e,w;w=e=0;
            scanf("%d",&t);
            tt=t;
            while(tt%2==0&&tt!=0){
                tt=tt/2;
                e++;
            }
            er[i][j]=e;
             tt=t;
            while(tt%5==0&&tt!=0){
                tt=tt/5;
                w++;
            }
            wu[i][j]=w;
           // dp[i][j]=er[i][j];
        }
    }
     for(int i=0;i<=n+1;i++){
        dp[0][i]=INF;
        dp[n+1][i]=INF;
     }
     for(int i=0;i<=n+1;i++){
        dp[i][0]=INF;
        dp[i][n+1]=INF;
     }
     for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

        if(i==1&&j==1)
        {
            dp[1][1]=er[i][j];
            continue;
        }
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+er[i][j];

        }
     }
   //   cout<<dp[n][n]<<endl;




        for(int i=0;i<=n+1;i++){
        dp1[0][i]=INF;
        dp1[n+1][i]=INF;
     }
     for(int i=0;i<=n+1;i++){
        dp1[i][0]=INF;
        dp1[i][n+1]=INF;
     }
     for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){
if(i==1&&j==1)
        {
            dp1[1][1]=wu[i][j];
            continue;
        }
                dp1[i][j]=min(dp1[i-1][j],dp1[i][j-1])+wu[i][j];

        }
     }
     // cout<<dp1[n][n]<<endl;

     // cout<<ans<<endl;
     ll ans=min(dp[n][n],dp1[n][n]);
     printf("%lld\n",ans);
    return 0;
}