2016-11-14试题解题报告

By shenben

T1：

30%: O(n ^ 2 * m)暴力判断。

100%: 很显然答案的可能性最多只有n种，所以我们将所有人的答案按字典序排序后枚举。将每个人的答案作为正确答案来进行判断。

由于是判断题，若当前人的答案为正确答案则零分者的答案也就确定了，那么只需统计出这两种答案的人数判断是否满足题意，即可。这一步使用字符串哈希即可解决。

T2:

30%：枚举每个数所在的集合或者不选，然后判定即可。复杂度O(n*3^n)。

60%： Dp，两个数相等就相当于两个数的xor为0。设 f[i][j][k=0..2]代表处理到第 I 个数，如果 k = 1代表and值为j,如果k = 2代表xor 值为 j,如果k = 0则代表一个元素都没取。所以很容易得到方程：

f[i][j][0] = f[i + 1][j][0]

f[i][j & ai][1] = f[i + 1][j][1] + f[i + 1][j][0] + f[i + 1][j & ai][1]

f[i][j ^ ai][2] = f[i + 1][j][1] + f[i + 1][j][2] + f[i + 1][j ^ ai][2];

最后f[1][0][2]就是答案, 复杂度为O(n * 1024 * 3)

DP还可以分开用f[i][j]和g[i][j]表示前i个xor值为j，后i个and值为j的方案数，随后枚举分界点k来求总方案数。复杂度O(n * 1024 * 3)。

100%：满分数据需要高精，答案位数较大，需要进行压位来防止TLE，因为不知道答案的位数究竟多大，压位后高精数组仍需要开的较大一些，所以原DP的数组滚动即可。

T3：

30%：

当T<= 10000的时候，可以设 vis[i][j] 代表到达第i个点时间为j是否合法。这样是O(T*m)，可以拿到小数据。

另外的那30%：各种奇怪的骗分方法。选手自行考虑。

100%：

当T很大的时候，我们考虑如果0 -> x -> n - 1路径时间为T，且从x出发有一个时间为d的环，则一定存在一个K满足 K + p*d = T（至少T满足条件），这样我们就能绕着环走p次就能构成一条时间为T的路径。

显然要求的路径一定经过 0，而且在合法情况下从0号点出发一定存在一条边，否则0号点和n - 1号就是不联通的。随便取一条边时间为d, 则能构成从0号点出发的一个时间为2d的环。这样原题就化为最短路问题了，dis[i][j] 代表到达i号点，时间为 j + p * 2d，最小的 j+p*2d，

最后判断dis[n -1][T % 2d] 是否小于等于T即可。

实际上就是在30%的基础上缩减状态。

时间复杂度为O(m*d)。

T1代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long 
#define R register
#define debug(x) cout<<x<<"---"<<endl
inline int read(){
    R int x=0;bool f=1;
    R char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f?x:-x;
} 
const int N=30000+5;
const int M=3000+5;
string s[N];
map<string,int>ys;
string s1,t;
int n,m,p,q;
int cnt,ans;
char ss[M];
int judge(string &std,string &now){
    int res=0;
    for(int i=0;i<m;i++) if(std[i]!=now[i]) res++;
    return res;
}
void fanzhuan(){
    for(int slen=s1.length(),i=0;i<slen;i++){
        s1[i]=(s1[i]=='N'?'Y':'N');
    }
    printf("%s",s1.c_str());
}
void sp(int x){
    if(x==m){
        int j,t;
        for(j=1;j<=cnt;j++){
            if(s[j]==s1) break;
            t=judge(s1,s[j]);
            if(t==m) break;
        }
        if(j>cnt){for(int i=0;i<m;i++) putchar(s1[i]);exit(0);}
        return ;
    }
    for(int i=0;i<2;i++){
        s1[x]=(!i?'N':'Y');
        sp(x+1);
    } 
}
void in(){
    char ch;int l=0;
    for(ch=getchar();l<m;ch=getchar()){
        if(ch!='
') ss[l++]=ch;
        else break;
    }
    ss[l]='

2016-11-14试题解题报告

相关推荐