看心情填坑

下午政选选活，果断翘一个下午，又打了一场

能力有限，只写我做的或者看了的几道。

http://codeforces.com/gym/100814

这场gym真是邪了，一群人不去做简单的先做什么吊得飞起的可持久化并查集

A Arcade Game

题意：给你一个最多⑨位数，然后你每次操作会得到一个这⑨个数的排列，然后先判断你得到的数是否比你之前得到的每一个数都严格大于，不符合的话你就输了，然后判断你得到的数是否是排列里可以得到的数的最大的，假如说是的话游戏结束你获得胜利，问你赢的期望是多少。⑨位精度

这个不是沙雕概率DP吗。。。直接dp[i]表示第i大的排列，dp[i]=\(\sum_{k=1}^{i-1}dp[k]/n!\)初始化dp[1]=1,只要注意假如是第一大的话要输出0就行了。

然后我这个沙雕这样干，然后就T掉了9!=362880我O((n!)^2)去做我已经不知道我在想什么了。。。直接dp[2]=1/n!,dp[k]=dp[k-1]*(1+1/n!)就好了。。。

#include<cstdio>
#include<cstring>
using namespace std;
char s[20];
int jc[11];
int test,n,m;
long double ans[400000],p;
bool b[10];
int work(int k){
	if(k==n-1)return 0;
	int a=s[k]-'0',S=0;
	for(int i=9;i>s[k]-'0';i--)if(b[i])S++;
	b[s[k]-'0']=false;
	int ans=work(k+1);
	b[s[k]-'0']=true;
	return ans+jc[n-k-1]*S;
}
int main(){
	scanf("%d",&test);
	jc[0]=1;
	for(int i=1;i<=9;i++)jc[i]=jc[i-1]*i;
	while(test--){
		for(int i=0;i<=9;i++)b[i]=false;
		scanf("%s",&s);
		bool Ans=true;
		n=strlen(s);
		for(int i=1;i<n;i++)if(s[i]>s[i-1])Ans=false;
		if(Ans){
			printf("0.000000000\n");
			continue;
		}
		for(int i=0;i<n;i++)b[s[i]-'0']=true;
		int s=1;
		for(int i=1;i<=n;i++)s*=i;
		m=work(0);
		p=1;ans[1]=1.0/jc[n];
		for(int i=2;i<=m;i++)ans[i]=ans[i-1]*(1+1.0/jc[n]);
		printf("%.9lf\n",double(ans[m]));
	}
}

B Unlucky Teacher

题意：有m道题是A、B、C、D其中一个，给你n*m个信息告诉你第k个位置一定是什么或者一定不是什么。求这m道题答案是什么，不确定输出问号

别和我说你不会做，代码都不想放。

C Connecting Graph

题意：n个点m个操作，第一种操作两点之间连一条边，第二个操作问你两个点是什么时候开始联通的。

做完最傻的几个发现C过的人的人最多（3个），就去做C，然后就被屌傻了。

感觉是CDQ之类的东西，想了一下不会来，就没有写

D rozen Rivers

题意：现在有一个树形结构的河流，从根节点1开始解冻，初始解冻速度为1单位长度每秒，每解冻完一条边这条边上的父节点连出的其它还没解冻完的边解冻速度变为1/2单位长度每秒，m个询问，询问到时间t为止有几个叶子节点解冻。

一开始题意看错。。。以为是只在这个节点后面的解冻速度变为二分之一。。。然后TLE2+RE2+WA2三连发。

然后又题意看错。。。以为是一条边解冻完所有都变成1/2，好像要上堆搞还好没有写

这TM不是个傻题吗(╯‵□′)╯︵┻━┻DFS一遍把所有叶子节点解冻时间搞出来查询直接二分(╯‵□′)╯︵┻━┻

然后写完E题还有19分钟而且当时我还处于第二个看错提议的状态，然后就没有写。

E Palmyra

不知道为什么做的人少的傻题

题意：有一个n*m矩阵，你要从左上走到右下，不是向右就是向下，每个位置有一个p_i,j,你要找到一条路径的\(\prod p[i][j]\)转化成6进制之后后缀0尽可能多。

p_i,j只有1000，也就是说最多3⁶，然后感觉可以DP，100*100*6*(100+100-1)=11940000，多组数据有点方，然后就max[i][j]表示到第i行第j列最多的3的幂次，min[i][j]表示到第i行第j列最少的3的幂次，预处理出来之后dp应该会快很多吧。然后中间还因为这个东西WA了几发，交上去的时候还有点方他要放100组数据我也没办法

31ms呵呵

#include<cstdio>
#include<cstring>
using namespace std;
int dp[101][101][1195];
int n,m,a[101][101],b[101][101],Max[101][101],Min[101][101];
int ans,test,x;
int main(){
	scanf("%d",&test);
	while(test--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				scanf("%d",&x);
				a[i][j]=b[i][j]=0;
				while(x%2==0){
					x>>=1;
					a[i][j]++;
				}
				while(x%3==0){
					x/=3;
					b[i][j]++;
				}
			}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)if(Max[i-1][j]>Max[i][j-1])Max[i][j]=Max[i-1][j]+b[i][j];
			else Max[i][j]=Max[i][j-1]+b[i][j];
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				if(i==1){
					Min[i][j]=Min[i][j-1]+b[i][j];
					continue;
				}
				if(j==1){
					Min[i][j]=Min[i-1][j]+b[i][j];
					continue;
				}
				if(Min[i-1][j]>Min[i][j-1])Min[i][j]=Min[i][j-1]+b[i][j];
				else Min[i][j]=Min[i-1][j]+b[i][j];
			}
		dp[1][1][b[1][1]]=a[1][1];
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				if((i==1)&&(j==1))continue;
				for(int k=Min[i][j];k<=Max[i][j];k++){
					dp[i][j][k]=-2000000000;
					if((i>1)&&(k-b[i][j]<=Max[i-1][j])&&(k-b[i][j]>=Min[i-1][j]))dp[i][j][k]=dp[i-1][j][k-b[i][j]]+a[i][j];
					if((j>1)&&(k-b[i][j]<=Max[i][j-1])&&(k-b[i][j]>=Min[i][j-1])&&(dp[i][j-1][k-b[i][j]]+a[i][j]>dp[i][j][k]))dp[i][j][k]=dp[i][j-1][k-b[i][j]]+a[i][j];
				}
			}
		ans=0;
		for(int i=Min[n][m];i<=Max[n][m];i++)if((i>ans)&&(dp[n][m][i]>ans)){
			if(i<dp[n][m][i])ans=i;
			else ans=dp[n][m][i];
		}
		printf("%d\n",ans);
	}
}

F Geometry

我大概花了1分钟搞这道题，包括写这行字。

J Game

J是沙雕的啊----F老板语录

不知道J题这种沙雕题为什么没人做

题意：长度为10000的字符串，两个人玩游戏，每次操作会可以选择第1个和第2个，第3个和第4个...第2*i-1个和第2*i个合并，或者选择第len个和第len-1个，第len-2个和第len-3个以此类推合并，2个字母合成一个的26*26的表给出，最后显然一定会剩下一个字母，这个字母是元音字母的话先手获胜，否则后手获胜，问最后谁会获胜。

一开始题意看错以为最后操作的人假如得到元音就赢否则输怒WA三发每次字符串操作完会变成二分之一长度，那么显然最多log次。

马萨卡，好像暴力模拟搜索就行，复杂度O(nlogn)这种沙雕题为什么做的人这么少

#include<cstdio>
#include<cstring>
using namespace std;
char a[30][30];
struct cao{
	char s[10005];
}s;
int test;
bool work(cao s,int k){
	int n=strlen(s.s);
	if(n==1)return (s.s[0]=='a')||(s.s[0]=='e')||(s.s[0]=='i')||(s.s[0]=='o')||(s.s[0]=='u');
	cao tmp;
	for(int i=0;i<n/2;i++)tmp.s[i]=a[s.s[i*2]-'a'][s.s[i*2+1]-'a'];
	if(n&1)tmp.s[n/2]=s.s[n-1],tmp.s[n/2+1]=0;
	else tmp.s[n/2]=0;
	bool ans=work(tmp,1-k);
	if((ans)&&(k==1))return ans;
	if((!ans)&&(k==0))return ans;
	if(n%2==0)return ans;
	tmp.s[0]=s.s[0];
	for(int i=1;i<=n/2;i++)tmp.s[i]=a[s.s[i*2-1]-'a'][s.s[i*2]-'a'];
	tmp.s[n/2+1]=0;
	return work(tmp,1-k);
}
int main(){
	scanf("%d",&test);
	while(test--){
		for(int i=0;i<26;i++)scanf("%s",&a[i]);
		scanf("%s",&s.s);
		if(work(s,1))printf("Salah\n");
		else printf("Marzo\n");
	}
}