【WC2015】未来程序
这个题比较有意思，给你程序和输入，让你求输出。
直接F11，半分钟后，意识到事情不是那么简单。
五分钟后，重新看看题面
example
样例都做不出来可以弃疗了。。。
testdata 1
很容易发现，程序要求的是
等价程序：
void _(){
unsigned long long a,b,c,d;
scanf("%I64u%I64u%I64u",&a,&b,&c);
for(d=0;b;a=(a+a)%c,b>>=1)
if(b&1)d=(d+a)%c;//类似快速幂
printf("%I64u\n",d);
}testdata 2
观察以下代码
b = a + b;
a = 2 * b - a + c;
c = 2 * b - a + c;略加思索
a-->a+2b+c
b-->a+b
c-->a下面的取膜写的那么复杂
矩阵快速幂解决！
Ps：这求的是Fib数列第(n-1)项的平方膜p的值。
等价程序：
typedef long long LL;
LL n,p;
struct mat{
LL c[3][3];
void clear(){
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
c[i][j]=0;
}
}I,Ans;
mat operator *(const mat &a,const mat &b){
mat pG;
pG.clear();
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
pG.c[i][j]=(pG.c[i][j]+a.c[i][k]*b.c[k][j])%p;
return pG;
}
void _______(){
scanf("%I64d%I64d",&n,&p);
Ans.clear();
Ans.c[0][2]=1;//答案矩阵
I.clear();
I.c[0][2]=I.c[1][1]=I.c[2][0]=I.c[2][1]=I.c[2][2]=1;
I.c[1][2]=2;//递推矩阵
for(;n;I=I*I,n>>=1)
if(n&1)Ans=Ans*I;
printf("%I64d\n",(Ans.c[0][2]-Ans.c[0][1]*2+Ans.c[0][0]+p+p)%p);
}testdata 3
容易发现这是自然数幂求和。
直接套公式：
然而直接写只有6分或8分！
需要将分母做gcd来消去。
但是我们会发现最后一个
于是用
Ps:三次方是一次方的平方
等价程序：
unsigned long long s0,s1,s2,s3,s4,i,j,n;
typedef unsigned long long ULL;
ULL gcd(ULL u,ULL v){return v?gcd(v,u%v):u;}
int main() {
scanf("%I64u", &n);
s0=n+1;
i=2;
s1=n/gcd(n,i);i=i/gcd(n,i);
s1=(n+1)/gcd(n+1,i)*s1;
i=6;
s2=n/gcd(n,i);i/=gcd(n,i);
s2=(n+1)/gcd(n+1,i)*s2;i/=gcd(n+1,i);
s2=(2*n+1)/gcd(2*n+1,i)*s2;
s3=s1*s1;//三次方是一次方的平方
i=30;
s4=n/gcd(n,i);i/=gcd(n,i);
s4=(n+1)/gcd(n+1,i)*s4;i/=gcd(n+1,i);
s4=(2*n+1)/gcd(2*n+1,i)*s4;i/=gcd(2*n+1,i);
if(i==5){
j=(n-1)/gcd(n-1,i);i/=gcd(n-1,i);
j=(n+2)/gcd(n+2,i)*j;
j=j*3+1;
}else j=3*n*(n+1)-1;
//分两种情况特判一下
s4=s4*j;
printf("%I64u\n%I64u\n",s0,s0);
printf("%I64u\n%I64u\n",s1,s1);
printf("%I64u\n%I64u\n",s2,s2);
printf("%I64u\n%I64u\n",s3,s3);
printf("%I64u\n%I64u\n",s4,s4);
return 0;
}testdata 4
阅读程序，发现给了一个
第一问：对于每一个
很显然，假设有
第二问：对于每一个
我们用DP求解。
转移方程分别为
然后对于每个
另外，为了不判边界，我把
等价程序：
long long count1(){
long long ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(data[i][j])ans++;
return ans*(ans-1);
//直接套公式
}
const int M=5050;
int dis[M][M],rdis[M][M];
int min(int u,int v){return u<v?u:v;}
void dp1(){//左上-->右下
memset(rdis,0x3f,sizeof(rdis));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(data[i][j]){
rdis[i][j]=min(rdis[i-1][j],rdis[i][j-1])+1;
dis[i][j]=min(dis[i][j],rdis[i][j]);
}else rdis[i][j]=0;
}
void dp2(){//右上-->左下
memset(rdis,0x3f,sizeof(rdis));
for(int i=1;i<=n;i++)
for(int j=m;j>=1;j--)
if(data[i][j]){
rdis[i][j]=min(rdis[i-1][j],rdis[i][j+1])+1;
dis[i][j]=min(dis[i][j],rdis[i][j]);
}else rdis[i][j]=0;
}
void dp3(){//左下-->右上
memset(rdis,0x3f,sizeof(rdis));
for(int i=n;i>=1;i--)
for(int j=1;j<=m;j++)
if(data[i][j]){
rdis[i][j]=min(rdis[i+1][j],rdis[i][j-1])+1;
dis[i][j]=min(dis[i][j],rdis[i][j]);
}else rdis[i][j]=0;
}
void dp4(){//右下-->左上
memset(rdis,0x3f,sizeof(rdis));
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--)
if(data[i][j]){
rdis[i][j]=min(rdis[i+1][j],rdis[i][j+1])+1;
dis[i][j]=min(dis[i][j],rdis[i][j]);
}else rdis[i][j]=0;
}
long long count2(){
long long ans=0;
memset(dis,0x3f,sizeof(dis));
dp1();dp2();dp3();dp4();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(data[i][j])ans+=dis[i][j];
return ans;
}testdata 5
阅读程序，发现和第四题有点像。
只不过要求的是
n^6复杂度自闭啊。。
很容易考虑到单调栈做法：我们处理出每个
等价程序：
long long a[N][N],Ans,ans;
typedef pair<int,int>pr;
stack<pr>s;
void clear(){while(s.size())s.pop();ans=0;}
long long count3(){
Ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=data[i][j]*(a[i-1][j]+1);
//处理每个1向上的最大延伸长度
for(int i=1;i<=n;i++){
clear();//清空一下
for(int j=1;j<=m;j++){
if(!a[i][j]){clear();continue;}//该点为0，清空栈
int siz=1;
while(s.size()&&s.top().first>=a[i][j]){
siz+=s.top().second;
ans-=s.top().first*s.top().second;
s.pop();
}
//不能作为左上端点的减去
s.push(pr(a[i][j],siz));//插入
ans+=a[i][j]*siz;
Ans+=ans;//计算答案
}
}
return Ans;
}testdata 6
可以说是花时间最多的一个点。。
不会Floyd判圈还特意去学了
一个初步的想法是用map，电脑卡爆啦，显然不能得到满分。
考虑Brent判圈。(不会自学，逃:)
Floyd：？？？
然后跑344s出了答案
等价程序：
#include<cstdio>
typedef unsigned long long ULL;
ULL T,n,a,b,c;
ULL s,t,tim,tim_n,tim_m;
int main(){
for(T=10;T;T--){
scanf("%I64u%I64u%I64u%I64u",&n,&a,&b,&c);
s=t=0;
tim_n=0;tim_m=2;
while(true){//Brent的思想：倍增
t=(a*t*t+b)%c;
++tim_n;
if(s==t)break;
if(tim_n==tim_m){
tim_n=0;
tim_m<<=1;
s=t;
}
}
//tim_n->循环节长度
s=t=0;tim=0;
while(tim<tim_n){
t=(a*t*t+b)%c;
++tim;
}
tim=1;
while(s!=t){
s=(a*s*s+b)%c;
t=(a*t*t+b)%c;
++tim;
}
tim_m=(n-tim)%tim_n+1;
//tim->环的起点 s->起点的值
tim=1;
while(tim<=tim_m)s=(a*s*s+b)%c,++tim;
printf("%I64u\n",s);
}
}testdata 7
"字母"独？直接暴力搜索！
敲过数独的可以直接切了。
正搜TLE，倒搜5.7s
不知道DLX跑的快不快
等价程序：
#include<cstdio>
const int N=20;
int _2[N];
int f[N],g[N],h[N],opt;
char s[N][N];
int How(int u,int v){
return (u/4)*4+v/4;
}
void dfs(int x,int y){
if(x==-1){opt=1;return;}
if(!opt&&s[x][y]!='?'){
if(y==0)dfs(x-1,15);
else dfs(x,y-1);//倒搜
// dfs(x+(y+1)/16,(y+1)&15);正搜
}
else{
for(int i=0;i<16;i++)
if(!opt&&(f[x]&_2[i])&&(g[y]&_2[i])&&(h[How(x,y)]&_2[i])){
f[x]^=_2[i];
g[y]^=_2[i];
h[How(x,y)]^=_2[i];
s[x][y]='A'+i;
if(y==0)dfs(x-1,15);
else dfs(x,y-1);//倒搜
// dfs(x+(y+1)/16,(y+1)&15);正搜
if(!opt)s[x][y]='?';
f[x]^=_2[i];
g[y]^=_2[i];
h[How(x,y)]^=_2[i];
}
}
}
void solve(int points){
for(int i=0;i<16;i++)f[i]=g[i]=h[i]=_2[16]-1;//初始化
for(int i=0;i<16;i++){
scanf("%s",s[i]);
for(int j=0;j<16;j++)
if(s[i][j]!='?'){
f[i]^=_2[s[i][j]-'A'];
g[j]^=_2[s[i][j]-'A'];
h[How(i,j)]^=_2[s[i][j]-'A'];//压缩一下状态
}
}
opt=0;
dfs(15,15);//倒搜
if(opt){
for(int k=0;k<points;k++){
for(int i=0;i<16;i++)
printf("%s", s[i]);
putchar('\n');
}
}else{
for(int k=0;k<points;k++)
printf("NO SOLUTION.\n");
}
}
int main(){
_2[0]=1;
for(int i=1;i<N;i++)_2[i]=_2[i-1]<<1;
//预处理2的次幂
solve(1);
solve(2);
solve(3);
solve(4);
return 0;
}testdata 8
看起来好像是组合数的题？
嗯。。跑个小数据，差分一下。。
唉？？看起来这些都是关于
然后我们通过大眼观察和暴力枚举因式的方法，得到了答案！
我还手算七次方程
OEIS：？？？
pro1
pro2
pro3
pro4
pro5
pro6
pro7
pro8
pro9
pro10
花了我一个多小时
等价程序：
#include<cstdio>
typedef unsigned long long ULL;
ULL n,p=1234567891;
ULL ksm(ULL u,ULL v){
ULL res=1;
for(;v;v>>=1,u=u*u%p)
if(v&1)res=res*u%p;
return res;
}
int main() {
scanf("%I64u",&n);n%=p;
printf("%I64u\n",n>6?(n*(n-1)%p*(n-2)%p*(n-3)%p*(n-4)%p*(n-5)%p*(n-6)%p*ksm(5040,p-2)%p):0);
printf("%I64u\n",n>1?((n-1)*(n-1)%p*n%p*n%p*(2*n-1)%p*(2*n%p*n%p-2*n%p+1+p)%p*ksm(60,p-2)%p):0);
printf("%I64u\n",n>2?(n*n%p*(n-1)%p*(n-1)%p*(n-2)%p*(2*n-1)%p*(7*n-3)%p*ksm(360,p-2)%p):0);
printf("%I64u\n",n>2?(n*n%p*n%p*(n-1)%p*(n-1)%p*(n-2)%p*(3*n-1)%p*ksm(48,p-2)%p):0);
printf("%I64u\n",n>3?(n*n%p*n%p*n%p*(n-1)%p*(n-2)%p*(n-3)%p*ksm(24,p-2)%p):0);
printf("%I64u\n",n>2?(n*n%p*n%p*(n-1)%p*(n-2)%p*(3*n*n%p-6*n%p+1+p)%p*ksm(60,p-2)%p):0);
printf("%I64u\n",n>3?(n*n%p*(n-1)%p*(n-2)%p*(n-3)%p*(5*n*n%p-9*n%p+1+p)%p*ksm(360,p-2)%p):0);
printf("%I64u\n",n>1?(n*n%p*(n-1)%p*(n-1)%p*(2*n-1)%p*(5*n%p*n%p-5*n%p+2+p)%p*ksm(144,p-2)%p):0);
printf("%I64u\n",n>2?(n*n%p*n%p*(n-1)%p*(n-1)%p*(n-2)%p*(2*n-1)%p*ksm(36,p-2)%p):0);
printf("%I64u\n",n>3?(n*n%p*(n-1)%p*(n-1)%p*(n-2)%p*(n-3)%p*(2*n-3)%p*ksm(240,p-2)%p):0);
return 0;
}testdata 9
这个点比较特殊，又分为10个子问题。
而且还给你了答案的MD5加密，这就可以验证自己的答案对不对了。
当然你可以选择暴力解密
暴力枚举答案验证MD5也可以
pro1：
问第一年NOI是哪年。。1984啊，笔试板子
pro2：
问最常见的6位密码。。123456啊，常识
pro3：
问大头照是谁。。chenlijie啊，大眼观察法裸题
pro4：
问3个可见符号。。一共`~!@#$%^&*()_+-={}[]\|;:'",<.>/?
暴枚$_$
pro5~8：
啥？？？名言？？我怎么知道
别慌，分析一下。还是不知道
突然发现在testdata 2中有一部伪英语词典，直接爆搜。mmp
答案依次是we hold these truths
这四个pro的程序：
while(scanf("%s",ss[cnt])!=EOF)cnt++;
for(int i=0;i<cnt;i++){
unsigned char example[strlen(ss[i])+1];//注意+1！
int LEN=strlen(ss[i]);
for(int j=0;j<LEN;j++)example[j]=ss[i][j];
example[LEN]='\0';//注意\0！
MD5_CTX md5;
MD5Init(&md5);
MD5Update(&md5,example,strlen((char *)example));
MD5Final(&md5,e);
char Ans[32];
for(int j=0;j<16;j++){
int pG=e[j]/16;
if(pG<10)Ans[j*2]=pG+48;
if(pG>=10)Ans[j*2]=pG-10+97;
pG=e[j]%16;
if(pG<10)Ans[j*2+1]=pG+48;
if(pG>=10)Ans[j*2+1]=pG-10+97;
}
if(strcmp(Ans,"ff1ccf57e98c817df1efcd9fe44a8aeb")==0){
printf("5 %s\n",ss[i]);
continue;
}
if(strcmp(Ans,"af1d8213f4a22b0f9803fec9259ff7a8")==0){
printf("6 %s\n",ss[i]);
continue;
}
if(strcmp(Ans,"bd4c4ea1b44a8ff2afa18dfd261ec2c8")==0){
printf("7 %s\n",ss[i]);
continue;
}
if(strcmp(Ans,"566d8cef537b35c5c84e93d5e5aebaf3")==0){
printf("8 %s\n",ss[i]);
continue;
}
if(strcmp(Ans,"c3f45d94e808f61ae955318aed53bf95")==0){
printf("10 %s\n",ss[i]);
continue;
}但是第10个搜不出来
pro9：
仿照pro 5~8，爆搜即可。答案为to be
但是我没搜
pro10：
不会做
其实如果你历史和英语足够好，就能答出来了
如果你又做了第10个点，就会在第7054行发现答案！
7053 balalala....
7054 WE(); HOLD(); THESE(); TRUTHS(); TO(); BE(); SELFEVIDENT(); balalala...
7055 balalala...所以答案是selfevident
总结：考验脑洞
等价程序：
#include<cstdio>
int main(){
printf("\
1984\n\
123456\n\
chenlijie\n\
$_$\n\
we\n\
hold\n\
these\n\
truths\n\
to be\n\
selfevident\n\
");
}无耻的做法是上网找一个MD5解密器
testdata 10
好的，我们来看最后一个点。。。
WC? 嗯，确实是WC
ALGORITHM? 排序？
A QUICK BROWN FOX JUMPS OVER THE LAZY DOG?
一只棕色的狐狸快速跳过了一条懒惰的狗？啥意思？好吧这句话包含了26个字母。
下面是.......独立宣言？震惊！出题人有多无聊
冷静分析。。。
首先上面太暴力，要改一改。
ULL p[30],sum;
p[0]=1;
for(ULL i=1;i<=26;i++){
sum+=p[i-1];
p[i]=p[i-1]*(26-i)+sum;
printf("void %c(){__=__+___*%I64uull;}\n",64+(int)i,p[i]);
}得到
void _(){__=__+___*1ull;}
void A(){__=__+___*26ull;}
void B(){__=__+___*651ull;}
void C(){__=__+___*15651ull;}
void D(){__=__+___*360651ull;}
void E(){__=__+___*7950651ull;}
void F(){__=__+___*167340651ull;}
void G(){__=__+___*3355140651ull;}
void H(){__=__+___*63923340651ull;}
void I(){__=__+___*1154150940651ull;}
void J(){__=__+___*19688020140651ull;}
void K(){__=__+___*316229927340651ull;}
void L(){__=__+___*4764358535340651ull;}
void M(){__=__+___*67038159047340651ull;}
void N(){__=__+___*876597565703340651ull;}
void O(){__=__+___*10591310445575340651ull;}
void P(){__=__+___*6772687681910030955ull;}
void Q(){__=__+___*5479948192676037227ull;}
void R(){__=__+___*12292036863279645291ull;}
void S(){__=__+___*11448514006979854955ull;}
void T(){__=__+___*5543854012881322603ull;}
void U(){__=__+___*7009382195709231723ull;}
void V(){__=__+___*14337023109848777323ull;}
void W(){__=__+___*6754098618987856491ull;}
void X(){__=__+___*2452069220114645611ull;}
void Y(){__=__+___*12294754496077775467ull;}
void Z(){__=__+___*3690695698331353707ull;}直接做不TLE才怪
继续观察。。。下面的单词调用的好像是不包含自己的子串，所以统计一下各个长度的单词每个字母的统计次数。。。