A - BBP Forluma

还没看

B - Bridge

在一个$2*n$的网格上$m$次加边或删边，并询问割边数量。$n,m\leq200000$。

C - Empty Convex Polygons

求$n$个点的最大空凸包。$n\leq50$。

枚举最下面一个点，可以对上面的点进行极角排序，那么可以用一个DP来做，$f[i][j]$表示当前点是$i$，上一个点是$j$的最大面积，再枚举下一个点，判断是否合法即可。注意边界情况的判断，因为点可以再边上。时间复杂度$O(n^4)$。不是我写的，有空写一发$n^3$的。

D - Defense of the Ancients

没看

E - Five-round Show Hand

德州扑克，有空写一发

F - Heron and His Triangle

$T$次让你找到面积比$n$大的边长为$t-1,t,t+1$且面积为整数的最小的三角形。$T\leq30000,n\leq10^{30}$

找规律发现$f_1=4,f_2=14,f_n=4f_{n-1}-f_{n-2}$，然后写个JAVA就好了

G - Infinite Fraction Path

没看

H - Legends of the Three Kingdoms

四个人玩三国杀，起始血量分别为$h_1,h_2,h_3,h_4$，轮流选择一个人让他血量$-1$，每个人都会选择让他胜率最高的决定，如果有多个选择将随机选择，血量为$0$死亡。求主公、内奸、反贼获胜的概率，$h_1,h_2,h_3,h_4<40$

直接四维DP即可，大力讨论一下，卡空间

I - Little Boxes

求四个数的和

J - New Self-describing Sequence

$a_1=1,a_n=a_{n-1}+G(a_{n-1})$，$G(x)$表示$x$的数位和，$s_n=\sum_{i=1}^na_i$。$T$次询问$a_n$和$s_n$，$n\leq10^{17}$，$T\leq32768$。神题

K - Rabbits

$n$个兔子在数轴上排成一列，每次选择最左边或最右边的兔子跳到中间的一个空格位置，问最多能跳多少次。$n\leq500$

很明显除了第一次得跳过很多空格，否则每个空格都利用，答案即$a_n-a_1-min(a_2-a_1,a_n-a_{n-1})-(n-2)$

L - Tree

给一颗$n$个点的无根树染$k$种颜色，问最多能有多少条边满足其两端每种颜色都有出现。

很显然如果删掉这条边后两个联通块都$>=k$那么这条边就可以，DFS一遍就好了。

#include<bits/stdc++.h>
#define N 222222
using namespace std;
int T,n,k,i,x,y,an,tot,fir[N],ne[N*2],la[N*2],sz[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
	sz[x]=1;
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa){
		dfs(la[i],x);
		sz[x]+=sz[la[i]];
	}
	if(min(sz[x],n-sz[x])>=k)an++;
}
int main(){
	for(scanf("%d",&T);T--;){
		scanf("%d%d",&n,&k);an=0;
		for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
		dfs(1,0);
		printf("%d\n",an);
		for(i=1;i<=n;i++)fir[i]=sz[i]=0;tot=0;
	}
}

M - Wandering Robots

有一个$N*N$的网格图，$K$个障碍点，每次随机游走或者停留（即最多5种选择，随机选一种），问能无穷步之后停留在斜上角的概率。$N\leq10000,K\leq1000$。

先让所有点走的概率都相同，然后随便走一步，状态就稳定了，走到每个点的概率就是其度数，那么对于障碍点修改一下周围点的度数，处理一下答案就好了，用map方便很多。

#include<bits/stdc++.h>
#define N 11111
#define LL long long
using namespace std;
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int T,n,k,x,y,i,j,ca,X[N],Y[N];
LL up,all,o;
map<int,int>mp[N];
int G(int x,int y){
	if((x==0||x==n-1)&&(y==0||y==n-1))return 3;
	if(x==0||x==n-1||y==0||y==n-1)return 4;
	return 5;
}
int main(){
	for(scanf("%d",&T);T--;){
		ca++;
		scanf("%d%d",&n,&k);
		all=5ll*(n-2)*(n-2)+4ll*(n-2)*4+3*4;
		up=8ll*(n-2)+3*3+5ll*(n-2)*(n-1)/2;

		for(i=1;i<=k;i++){
			scanf("%d%d",&x,&y);
			if(x+y>=n-1)up-=G(x,y);
			all-=G(x,y);

			mp[x][y]=ca;
			X[i]=x;Y[i]=y;
		}

		for(i=1;i<=k;i++){
			for(j=0;j<4;j++){
				x=X[i]+dx[j];y=Y[i]+dy[j];
				if(x>=0&&x<=n-1&&y>=0&&y<=n-1){
					if(mp[x][y]!=ca){
						all--;
						if(x+y>=n-1)up--;
					}
				}
			}
		}
		printf("Case #%d: ",ca);
		if(n==1)puts("1/1");else{
			o=__gcd(all,up);
			all/=o;up/=o;
			printf("%lld/%lld\n",up,all);
		}
	}
}

• 相关文章推荐
• 全局相关文章