XVIII Open Cup named after E.V. Pankratiev. GP of Romania

A. Balance

不難發現確定第一行第一列后即可確定全部，列不等式單純形求解線性規劃即可。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef vector<double>VD;
const int N=110;
const double eps=1e-9;
VD simplex(vector<VD>A, VD b, VD c){
	int n = A.size(), m = A[0].size() + 1, r = n, s = m - 1;
	vector<VD> D(n + 2, VD(m + 1, 0)); vector<int> ix(n + m);
	for(int i = 0; i < n + m; i ++) ix[i] = i;
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < m - 1; j ++) D[i][j] = -A[i][j];
		D[i][m - 1] = 1; D[i][m] = b[i];
		if(D[r][m] > D[i][m]) r = i;
	}
	for(int j = 0; j < m - 1; j ++) D[n][j] = c[j];
	D[n + 1][m - 1] = -1;
	for(double d; ;){
		if(r < n){
			int t = ix[s]; ix[s] = ix[r + m]; ix[r + m] = t;
			D[r][s] = 1.0 / D[r][s]; vector<int> speedUp;
			for(int j = 0; j <= m; j ++) if(j != s){
				D[r][j] *= -D[r][s];
				if(D[r][j]) speedUp.push_back(j);
			}
			for(int i = 0; i <= n + 1; i ++) if(i != r){
				for(int j = 0; j < speedUp.size(); j ++)
					D[i][speedUp[j]] += D[r][speedUp[j]] * D[i][s];
				D[i][s] *= D[r][s];
			}
		}
		r = -1; s = -1;
		for(int j = 0; j < m; j ++) if(s < 0 || ix[s] > ix[j])
			if(D[n + 1][j] > eps || (D[n + 1][j] > -eps && D[n][j] > eps)) s = j;
		if(s < 0) break;
		for(int i = 0; i < n; i ++) if(D[i][s] < -eps)
			if(r < 0 || (d = D[r][m] / D[r][s] - D[i][m] / D[i][s]) < -eps
				|| (d < eps && ix[r + m] > ix[i + m])) r = i;
		if(r < 0) return VD();
	}
	if(D[n + 1][m] < -eps) return VD();
	VD x(m - 1);
	for(int i = m; i < n + m; i ++) if(ix[i] < m - 1) x[ix[i]] = D[i - m][m];
	printf("%.0f\n",-D[n][m]);
	return x;	
}
int n,cnt,i,j,k;int a[N][N],f[N][N][N],s[N];double w[N];
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&a[i][j]);
	cnt=n*2-1;
	for(i=1;i<=n;i++){
		f[1][i][i]=1;
		if(i>1)f[i][1][i+n-1]=1;
	}
	for(i=2;i<=n;i++)for(j=2;j<=n;j++)for(k=1;k<=cnt;k++)f[i][j][k]=f[i-1][j][k]+f[i][j-1][k]-f[i-1][j-1][k];
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)for(k=1;k<=cnt;k++)s[k]+=f[i][j][k];
	VD c;
	vector<VD>A;
	VD b;
	for(k=1;k<=cnt;k++)c.push_back(-s[k]);
	for(i=1;i<=n;i++)for(j=1;j<=n;j++){
		b.push_back(-a[i][j]);
		VD t;
		for(k=1;k<=cnt;k++)t.push_back(-f[i][j][k]);
		A.push_back(t);
	}
	VD ret=simplex(A,b,c);
	for(i=1;i<=cnt;i++)w[i]=ret[i-1];
	for(i=1;i<=n;puts(""),i++)for(j=1;j<=n;j++){
		double t=0;
		for(k=1;k<=cnt;k++)t+=w[k]*f[i][j][k];
		printf("%.0f ",t);
	}
}
/*
4
1 1 1 1
1 1 1 1
1 1 1 0
1 1 1 1
*/

B. Entanglement

留坑。

C. Gravity

對于每個連通塊設$f_x$表示$x$連通塊往下掉了多少，對于同一列相鄰兩個關于$f$建圖求最短路即可。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 2020, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int n, m;
char s[N][N];
const int dy[4] = {-1,0,0,1};
const int dx[4] = {0,-1,1,0};
int id[N][N];
int ID;
void go(int y, int x)
{
	id[y][x] = ID;
	for(int k = 0; k < 4; ++k)
	{
		int yy = y + dy[k];
		int xx = x + dx[k];
		if(s[yy][xx] == '#' && !id[yy][xx])
		{
			go(yy, xx);
		}
	}
}
int boty[N], boto[N];
int f[N * N];
vector< pair<int,int> >a[N * N];
struct A
{
	int x, dis;
	bool operator < (const A & b)const
	{
		return dis > b.dis;
	}
};
void ins(int x, int y, int z)
{
	a[x].push_back({y,z});
}
bool e[N * N];
void dijk()
{
	MS(f, 63);
	f[0] = 0;
	priority_queue<A>q;
	q.push({0, 0});
	MS(e, 0);
	while(!q.empty())
	{
		int x = q.top().x; q.pop(); 
		if(e[x])continue; e[x] = 1;
		for(auto it : a[x])
		{
			int y = it.first;
			int z = it.second;
			if(f[x] + z < f[y])
			{
				f[y] = f[x] + z;
				q.push({y, f[y]});
			}
		}
	}
	//puts("dijk finish");
}
char ans[N][N];
int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		MS(s, 0);
		MS(id, 0);
		ID = 0;
		for(int i = 1; i <= n; ++i)
		{
			scanf("%s", s[i] + 1);
		}
		for(int i = 1; i <= n; ++i)
		{
			for(int j = 1; j <= m; ++j)
			{
				if(s[i][j] == '#' && !id[i][j])
				{
					++ID;
					go(i, j);
				}
			}
		}
		MS(boto, 0);
		for(int j = 1; j <= m; ++j)boty[j] = n + 1;
		for(int j = 1; j <= m; ++j)
		{
			for(int i = n; i >= 1; --i)if(s[i][j] == '#')
			{
				//printf("%d %d\n", i, j);
				int x = id[i][j];
				int y = boto[j];
				if(x != y)ins(y, x, boty[j] - i - 1);
				boto[j] = x;
				boty[j] = i;
			}
		}
		//continue;
		//puts("before dijk()");
		dijk();
		MS(ans, 0);
		for(int i = 1; i <= n; ++i)
		{
			for(int j = 1; j <= m; ++j)
			{
				ans[i][j] = '.';
			}
		}
		for(int i = 1; i <= n; ++i)
		{
			for(int j = 1; j <= m; ++j)if(s[i][j] == '#')
			{
				int x = id[i][j];
				//printf("%d %d %d\n", i, j, f[x]);
				ans[i + f[x]][j] = '#';
			}
		}
		for(int i = 1; i <= n; ++i)puts(ans[i] + 1);
		for(int i = 1; i <= ID; ++i)a[i].clear();
	}
	return 0;
}
/*
【trick&&吐槽】
10 10
..........
..######..
..#....#..
..#.#..#..
..#..#.#..
..#....#..
..######..
..........
..#....#..
.......#..

3 3
#.#
.#.
..#

6 6
######
.....#
.###.#
.###.#
.....#
######

【題意】


【分析】


【時間復雜度&&優化】


*/

D. Infinite Pattern Matching

枚舉位數，設$f[i][j][S]$表示還剩低$i$位未考慮，目前KMP指針為$j$，前面KMP轉移表為$S$是否搜過，記憶化搜索即可。

#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<cstdlib>
#include<iostream>
using namespace std;
typedef long long ll;
int g[2][60],ans;
map<string,int>f[100][60];
int m,i,j,k,nxt[60];char a[60],q[60];
ll pre;
int dfs(int n,int x,string s,int prelen,ll pre){
  if(!n){
    if(s[x]==m){
      for(int i=1;i<=prelen&&x<m;i++){
        x=g[q[i]][x];
        pre++;
      }
      cout<<pre;
      exit(0);
    }
    return s[x];
  }
  if(f[n][x].find(s)!=f[n][x].end())return f[n][x][s];
  int v=x;
  for(int i=0;i<2;i++){
    string o=s;
    q[prelen-n+1]=i;
    for(int j=0;j<=m;j++)o[j]=g[i][s[j]];
    v=dfs(n-1,v,o,prelen,pre);
    pre+=((ll)prelen)<<(n-1);
  }
  return f[n][x][s]=v;
}
int main(){
  scanf("%s",a+1);
  m=strlen(a+1);
  for(i=1;i<=m;i++)a[i]-='0';
  for(nxt[1]=j=0,i=2;i<=m;nxt[i++]=j){
    while(j&&a[j+1]!=a[i])j=nxt[j];
    if(a[j+1]==a[i])j++;
  }
  for(i=0;i<m;i++)for(j=0;j<2;j++){
    for(k=i;k&&a[k+1]!=j;k=nxt[k]);
    if(a[k+1]==j)k++;
    g[j][i]=k;
  }
  g[0][m]=g[1][m]=m;
  for(i=0;;i++){
    string o="";
    for(k=0;k<=m;k++)o.push_back(g[1][k]);
    q[1]=1;
    ans=dfs(i,ans,o,i+1,pre);
    pre+=((ll)(i+1))<<i;
  }
}

E. Inheritance

留坑。

F. Movies

留坑。

G. Origami

不難發現行列獨立，轉化為一維字符串問題。

對于一次折疊，就是邊界通過某個偶回文半徑進行了翻折，Manacher預處理出回文半徑后DP求出每個位置是否可以由左右邊界翻折得到即可。

時間復雜度$O(nm)$。

#include<cstdio>
typedef long long ll;
const int N=2000010;
int n,m,i,j,r,p,f[N],g[N],pre[N],suf[N];ll a[N],b[N],s[N];char ch[N];
inline int min(int a,int b){return a<b?a:b;}
ll solve(ll*a,int n){
  int m;
  for(i=1;i<=n;i++)s[i<<1]=a[i],s[i<<1|1]=-1;
  s[0]=-2;s[1]=-1;s[m=(n+1)<<1]=-3;
  for(r=p=0,f[1]=1,i=2;i<m;i++){
    for(f[i]=r>i?min(r-i,f[p*2-i]):1;s[i-f[i]]==s[i+f[i]];f[i]++);
    if(i+f[i]>r)r=i+f[i],p=i;
  }
  for(i=1;i<n;i++)g[i]=f[i<<1|1]>>1;
  for(pre[0]=i=1;i<n;i++){
    j=pre[i-1];
    if(i-g[i]-1>=0)j-=pre[i-g[i]-1];
    j=!!j;
    pre[i]=pre[i-1]+j;
  }
  ll ret=pre[n-1];
  for(suf[n]=1,i=n-1;i;i--){
    j=suf[i+1];
    if(i+g[i]+1<=n)j-=suf[i+g[i]+1];
    j=!!j;
    if(j)ret+=pre[i-1];
    suf[i]=suf[i+1]+j;
  }
  return ret;
}
int main(){
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;i++){
    scanf("%s",ch+1);
    for(j=1;j<=m;j++){
      a[i]=a[i]*233+ch[j];
      b[j]=b[j]*233+ch[j];
    }
  }
  printf("%lld",solve(a,n)*solve(b,m));
}

H. Qnp

留坑。

I. Salaj

最優策略下，一定是$1$到$j$作為一個SCC，$j+1$到$n$每個點作為一個SCC，然后$1$到$j$用了$k$個環才得到。

那么任意情況下，不影響SCC情況的多余邊數不能超過$\frac{n(n-1)+j(j-1)}{2}$。

設$f[i][j][k]$表示考慮了$i$條邊，$1$到$j$作為一個SCC，產生它用了$k$個環的方案數。

轉移則是要么將$j$往后擴，要么將當前邊作為多余邊，可以通過$i,j$和$k$很方便地得到可用邊數。

時間復雜度$O(n^3m)$，常數很小，可以通過，但可以通過前綴和優化到$O(n^2m)$。

#include<cstdio>
const int N=55,M=55*55;
int Case,n,m,P,i,j,k,x,y,f[M][N][N],lim[N],ans[M];
inline void up(int&a,int b){a=a+b<P?a+b:a+b-P;}
int main(){
	scanf("%d",&Case);
	while(Case--){
		scanf("%d%d%d",&n,&m,&P);
		if(P==1){
			for(i=1;i<=m;i++)printf("0 ");
			puts("");
			continue;
		}
		for(i=0;i<=m;i++)for(j=0;j<=n;j++)for(k=0;k<=n;k++)f[i][j][k]=0;
		for(i=0;i<=n;i++)lim[i]=(n*(n-1)+i*(i-1))/2;
		f[0][1][0]=1;
		for(i=0;i<=m;i++)ans[i]=0;
		for(i=0;i<=m;i++)for(j=1;j<=n;j++){
			if(i>lim[j])continue;
			for(k=0;k<=n;k++){
				if(!f[i][j][k])continue;
				up(ans[i],f[i][j][k]);
				up(f[i+1][j][k],f[i][j][k]);
				for(x=j+1;x<=n;x++){
					if(i+1-k<x)break;
					up(f[i+1][x][k+1],f[i][j][k]);
				}
			}
		}
		for(i=1;i<=m;i++)printf("%d ",ans[i]);
		puts("");
	}
}

J. Taxi

若已經確定了所有車和人的位置，則對于樹邊來說，經過它的對數為兩側車和人數量的較小值。

故枚舉每條樹邊，再枚舉一側的邊數，對于另一側的人數前綴和加速統計貢獻即可。

時間復雜度$O(n^2)$。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 2520, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
char s[N][N];
vector< pair<int,int> >a[N];
int sz[N];
void getsz(int x, int fa)
{
	sz[x] = 1;
	for(auto it : a[x])if(it.first != fa)
	{
		int y = it.first;
		getsz(y, x);
		sz[x] += sz[y];
	}
}
LL pw[N][N];
LL qpow(LL x, LL p)
{
	return pw[x][p];
	LL y = 1;
	while(p)
	{
		if(p & 1)y = y * x % Z;
		x = x * x % Z;
		p>>=1;
	}
	return y;
}
LL c[2505][2505];
LL C()
{
	c[0][0] = 1;
	for(int i = 1; i <= 2500; ++i)
	{
		c[i][0] = 1;
		for(int j = 1; j <= 2500; ++j)
		{
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % Z;
		}
	}
}
LL ans;
LL sml[N][N], big[N][N];
void init()
{
	for(int i = 0; i < N; ++i)
	{
		pw[i][0] = 1;
		for(int j = 1; j < N; ++j)
		{
			pw[i][j] = pw[i][j - 1] * i % Z;
		}
	}
	//peop
	for(int i = 0; i <= n; ++i)
	{
		for(int j = 0; j <= m; ++j)
		{
			sml[i][j] = qpow(i, j) * c[m][j] % Z * qpow(n - i, m - j) % Z * j % Z;
			if(j)gadd(sml[i][j], sml[i][j - 1]);
			big[i][j] = qpow(i, j) * c[m][j] % Z * qpow(n - i, m - j) % Z % Z;
		}
		for(int j = m - 1; j >= 0; --j)
		{
			gadd(big[i][j], big[i][j + 1]);
		}
	}
}
LL cal(int peo_p, int car)
{
	int car_p = n - peo_p;
	//情況一：peo <= car
	//peo * qpow(peo_p, peo) * qpow(car_p, m - peo)  前綴和
	
	//情況二：peo > car
	//car * qpow(peo_p, peo) * qpow(car_p, m - peo)  
	
	LL rtn = 0;
	/*
	for(int i = 0; i <= m; ++i)
	{
		gadd(rtn, qpow(peo_p, i) * c[m][i] % Z * qpow(car_p, m - i) % Z * min(i, car) % Z);
	}
	*/
	rtn = (sml[peo_p][car] + car * big[peo_p][car + 1]) % Z;
	return rtn;
}
void dfs(int x, int fa)
{
	for(auto it : a[x])if(it.first != fa)
	{
		int y = it.first;
		dfs(y, x);
		//枚舉下面的車的數量
		for(int botcar = 0; botcar <= m; ++botcar)
		{
			//得到上面的車的數量
			int topcar = m - botcar;
			
			//考慮了路徑的長度，考慮了車的放置方案數
			LL tmp = it.second * qpow(sz[y], botcar) % Z * qpow(n - sz[y], topcar)  % Z * c[m][topcar] % Z;
			
			//gadd(ans, tmp * cal(sz[y], topcar) % Z);
			gadd(ans, tmp * cal(n - sz[y], botcar) % Z);
		}
	}
}

int main()
{
	C();
	while(~scanf("%d%d", &n, &m))
	{
		init();
		for(int i = 1; i <= n; ++i)a[i].clear();
		for(int i = 1; i < n; ++i)
		{
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			a[x].push_back({y,z});
			a[y].push_back({x,z});
		}
		ans = 0;
		getsz(1, 0);
		//puts("before dfs");
		dfs(1, 0);
		printf("%lld\n", ans * 2 % Z);
	}
	return 0;
}
/*
【trick&&吐槽】
5 2
4 5 9805
3 4 2001
2 3 6438
1 3 3790

【題意】


【分析】


【時間復雜度&&優化】


*/

K. Tris

留坑。

L. Xormites

首先求出所有數的異或和$sum$，若先手拿到了$A$，則后手必然拿到了$sum\oplus A$。

若$sum=0$，則$A=sum\oplus A$，必定平局。

否則找到$sum$最高位的$1$，那么拿到奇數個$1$的一方獲勝，可以將所有數轉化為$0$和$1$。

若$n$是偶數，那么將序列黑白染色，必定有一方異或和較大，且先手可以保證自己拿走全部黑或者全部白，故先手必勝。

否則$n$是奇數，若$a_1$和$a_n$都是$0$，那么后手必然可以通過上述方法獲勝。

因此先手第一步必須要拿走一個$1$，接下來只能模仿對手行動，檢查是否可能即可。

時間復雜度$O(n)$。

#include<cstdio>
int Case,n,i,k,sum,a[50010];
bool check(int L,int R){
  int l=L,r=R,i,cnt=0;
  while(l<r&&a[l]==a[r])l++,r--;
  for(i=l;i<=r;i+=2)if(a[i]^a[i+1])return 0;
  for(i=L;i<=R;i++)cnt+=a[i];
  return cnt/2%2==0;
}
int solve(){
  scanf("%d",&n);
  sum=0;
  for(i=1;i<=n;i++){
    scanf("%d",&a[i]);
    sum^=a[i];
  }
  if(!sum)return 0;
  if(n%2==0)return 1;
  for(k=30;!(sum>>k&1);k--);
  for(i=1;i<=n;i++)a[i]=a[i]>>k&1;
  if(!a[1]&&!a[n])return -1;
  if(a[1]&&check(2,n))return 1;
  if(a[n]&&check(1,n-1))return 1;
  return -1;
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    int t=solve();
    if(t==1)puts("First");
    if(t==0)puts("Draw");
    if(t==-1)puts("Second");
  }
}

posted @ 2018-03-29 23:51 Claris 閱讀(1195) 評論(3) 收藏舉報

刷新頁面返回頂部

Claris' Blog

XVIII Open Cup named after E.V. Pankratiev. GP of Romania

公告