0608模拟算法试题

6.8模拟算法试题

测试说明

4个题目，3.5小时

以姓名命名文件夹，下存4个文件，分别命名。

1、洛谷 P1010 幂次方

题目描述

任何一个正整数都可以用2的幂次方表示。例如

    137=2^7+2^3+2^0

同时约定方次用括号来表示，即a^b 可表示为a(b)。

由此可知，137可表示为：

    2(7)+2(3)+2(0)

进一步：7= 2^2+2+2^0 (2^1用2表示)

    3=2+2^0

所以最后137可表示为：

    2(2(2)+2+2(0))+2(2+2(0))+2(0)

又如：

    1315=2^10 +2^8 +2^5 +2+1

所以1315最后可表示为：

    2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

输入输出格式

输入格式：

一个正整数n(n≤20000)。

输出格式：

符合约定的n的0，2表示(在表示中不能有空格)

输入输出样例

输入样例#1：

输出样例#1：

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

/*
先把所求转化为2进制,回溯模拟，注意判断‘+’是否该加
详见代码 
*/
#include<cstdio>
#include<iostream>
using namespace std;
long long n;
void search(long long x){
    int i=0,j=0;int a[101];
    if(!x) {cout<<0;return ;}
    while(x>0){
        if(x%2==1) a[j++]=i;//按位异或符 2^0->++ 转换二进制 
        x>>=1;
        i++;    
    }
    for(i=j-1;i>=0;i--){
        if(a[i]==1) cout<<"2";
        else{
            cout<<"2(";
            search(a[i]);//高位继续变低 直到<2 
            cout<<")";
            
        } 
        if(i!=0)cout<<"+";
    }
}
int main()
{
    long long n;
    cin>>n;
    search(n);
    return 0;
 }

2、codevs 1432 总数统计

题目描述 Description

给出n个数，统计两两之和小于k的方案数之和。

输入描述 Input Description

第一行一个数n，表示数字的个数；
第二行到第n + 1行，每行一个不超过2,000,000,000的数k；
第n + 2行一个数m，表示m个问题；
第n + 3行到第n + m + 2行，每行一个数m，询问表示n中两两组合不超过m的组
合的个数；

输出描述 Output Description

输出m行，每行对应一个答案

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

30%的数据1 ≤ n ≤ 100, 1 ≤ m ≤ 50, k ≤ 2000;
100%的数据 1 ≤ n ≤ 10000, 1 ≤ m ≤ 100, k ≤ 2,000,000,000;

/*
二分答案+sort     注意数据超int，要用long long 
思路:sort有序后二分
找一个对ans有贡献的数x（即<=k/2）
二分k-x的下界 那么之前的数与该数组合均可以构成一组合
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long num[101000],ans,n,m,k;
long long div(long long x){
    long long l=1,r=n+1;
    while(r-l>1){
        long long mid=(l+r>>1);
        if(num[mid]<=x) l=mid;
        else r=mid;
    }
    return l;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>num[i];
    }
    sort(num+1,num+n+1);
    cin>>m;
    while(m--){
        cin>>k;ans=0;
        for(int i=1;num[i]<=k/2;i++){
            long long x=div(k-num[i]);
            if(x>i) ans+=x-i;
        }
        printf("%lld
",ans);
    }
    return 0;
}

3、2835 挖金币游戏

题目描述 Description

这天，小X幸运地获得了一次进行挖金币游戏的机会，规则如下：

在一个N*N的矩形里，有N*N个边长为1的正方形格子。在游戏中取左下角的格子坐标为（1，1），右上角为（N,N）。在游戏开始前，每一个格子中都会放入一枚金币，而当游戏开始时，每一个格子中的那一枚金币都会进行一次移动，移动后的横、纵坐标值将分别变为原横、纵坐标值每一位上的乘积。当有金币被移动出格子矩形时，将被游戏方收走。小X将被允许选取M个格子，他将获得他所选取的格子中所有的金币，而他对游戏中获得的金币数有一个期望值H。他想知道他最多能获得的金币数能否达到他的期望值。不过金币移动的让人眼花缭乱，小X算不过来了，他找到了你，希望你能用编程解决这个问题。

输入描述 Input Description

一行，三个正整数数N、M、H，以空格隔开，意义如题目中所说

输出描述 Output Description

一个或两个正整数数，以空格隔开

若小X最多能获得的金币数能达到期望值（即大于等于），则输出小X最多能获得的金币数以及金币总数能达到期望值的格子数的最小值

若小X最多能获得的金币数不能达到期望值（即小于），则输出金币数最多的那个格子中的金币数

样例输入 Sample Input

17 3 10

样例输出 Sample Output

12 3

数据范围及提示 Data Size & Hint

对于20%的数据，保证0＜M≤N≤100

对于50%的数据，保证0＜M≤N≤2000

对于70%的数据，保证0＜M≤N≤5000

对于100%的数据，保证0＜M≤N≤10000

举例，（123,456）处的金币将会被移动至（1*2*3，4*5*6）即（6,120）。

/*解题思路：设f[i][j] 为移动后i，j上的金子数，
f[i][j]=g[i]*g[j]，g[i]是1到n中有多少数会转化为i，
然后从g*g的二维数组里找最大的M个。
//高级数据结构STL模拟+读入优化
//bian（）模拟变化*/ 
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define ll long long
#define Mo 1000000007
#define M 500000
#define pa pair<ll,int>
using namespace std;
ll read(){
    register ll x=0,f=1;
    register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
    
}
int n,m;
ll zui,shu,he,h,f[M];
int bian(int x){
    int ans=1;
    for(;x;){
          ans*=x%10;
          x/=10;
    }
    return ans;
}
int main(){
    n=read();
    m=read();
    h=read();
    for(int i=1;i<=n;i++){
          int a1=bian(i);
          if(a1>=1&&a1<=n)
             f[a1]++;
    }
    sort(f+1,f+n+1);
    priority_queue<pa,vector<pa>,less<pa> > q;
    for(int i=n;i>=0;i--)
        q.push(make_pair(f[n]*f[i],n));
    for(int i=1;i<=m;i++){
          int p=q.top().second;
          ll p1=q.top().first;
          if(i==1)
             zui=p1;
          he+=p1;
          if(he>=h&&!shu)
             shu=i;
        q.pop();
        if(p)
           q.push(make_pair(p1/f[p]*f[p-1],p-1));
    }
    if(shu)
      printf("%lld %lld
",he,shu);
    else
      printf("%lld
",zui);
    return 0;       
}

4、洛谷P1039 侦探推理

题目描述

明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：

证词中出现的其他话，都不列入逻辑推理的内容。

明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。

现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！

输入输出格式

输入格式：

输入由若干行组成，第一行有二个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，

每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写）。

往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。

输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。

输出格式：

如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。

输入输出样例

输入样例#1：

3 1 5

MIKE

CHARLES

KATE

MIKE: I am guilty.

MIKE: Today is Sunday.

CHARLES: MIKE is guilty.

KATE: I am guilty.

KATE: How are you??

输出样例#1：

MIKE

/*
检查：
1.记录已确定说谎人数，不说谎人数。
2. 怎么方便怎么来，不要想着会超时。永远0ms！
3. 函数返回值的时机。
处理数据！！：
1. 全说谎，全不说谎
2. 名字叫“GUILTY”、“I”、星期几、特别长
3. 证词一旦不与表中相同，就作废！（正确的证词后面加一点点点废话，你懂的）
4. 测点怎么没有人叫TODAY？…………
5 .数据一定要读完。
其他：
什么输出时多一个少一个空格神马的一定要注意。
*/
#include<cstdio>
#include<cstring>
#include<map>
#include<string>
using namespace std;
map<string,int>Map;
char s[105][25][525],name[105][525],ans[105][525],a[25][525];
int num[105],f[25],n,m,i,j,k,P,Today,flag,now,lie,Len,cnt,T;
char day[8][25]={"","Monday.","Tuesday.","Wednesday.","Thursday.","Friday.","Saturday.","Sunday."};
inline int equal(char *s1,char *s2){
    int l1=strlen(s1),l2=strlen(s2);
    if(l1!=l2) return 0;
    for(int i=0;i<l1;i++) 
        if(s1[i]!=s2[i]) 
            return 0;
    return 1;
}
inline int check_1(int k){
    if(!equal(s[k][num[k]],"guilty.")||num[k]<3||num[k]>4)
       return 2;
    if(s[k][1][0]!='I'||s[k][1][1]!=''||!equal(s[k][2],"am")) 
       return 2;
    if(num[k]==4) 
       if(!equal(s[k][3],"not")) 
          return 2;
    if(Map[name[k]]==now){
       if(num[k]==3) 
          return 0;
       return 1;
    }
    if(num[k]==3) 
       return 1;
    return 0;
}
inline int check_2(int k){
    if(!equal(s[k][num[k]],"guilty.")||num[k]<3||num[k]>4)
       return 2;
    if(!equal(s[k][2],"is")) 
       return 2;
    if(num[k]==4) if(!equal(s[k][3],"not")) 
       return 2;
    if(Map[s[k][1]]==now){
       if(num[k]==3) 
          return 0;
       return 1;
    }
    if(num[k]==3) 
       return 1;
    return 0;
}
inline int check_3(int k){
    if(num[k]!=3||!equal(s[k][1],"Today")||!equal(s[k][2],"is"))
       return 2;
    return equal(day[Today],s[k][3])^1;
}
inline int work(){
    now=Map[a[P]];
    int res=0,another=0;
    memset(f,0,sizeof(f));
    for(int i=1;i<=m;i++){
        int T1=check_1(i),T2=check_2(i),T3=check_3(i),pre=Map[name[i]];
        if(!T1||!T2||!T3){
            if(f[pre]==2) 
               return 0;
            f[pre]=1;
        }
        if(T1&1||T2&1||T3&1){
           if(f[pre]==1) return 0;
           f[pre]=2;
        }
    }
    for(int i=1;i<=n;i++)
        if(f[i]==2) res++;
        else if(!f[i]) another++;
    return (res<=lie&&res+another>=lie);
}
inline int OK(char ch){return (ch>='A'&&ch<='Z'||ch>='a'&&ch<='z');}
int main(){
    scanf("%d%d%d",&n,&lie,&m);
    for(i=1;i<=n;i++) scanf("%s",a[i]),Map[a[i]]=i;
    for(i=1;i<=m;i++) {
        scanf("%s",name[i]);name[i][strlen(name[i])-1]='';
        scanf("%s",s[i][num[i]=1]);
        while (OK(s[i][num[i]][strlen(s[i][num[i]])-1])) 
            scanf("%s",s[i][++num[i]]);
    }
    for(P=1;P<=n;P++){
        flag=0;
        for(Today=1;Today<=7&&!flag;Today++) 
            flag=work();
        if(flag) 
           memcpy(ans[++cnt],a[P],sizeof(a[P]));
    }
    if(!cnt) printf("Impossible");
    else if(cnt==1) printf("%s",ans[cnt]);
    else printf("Cannot Determine");
    return 0;
}