Petrozavodsk Winter-2018. Jagiellonian U Contest

2021-02-10 21:15

阅读：599

A. XOR

求出所有数的异或和$sum$，将所有数and上$sum$，然后求线性基，则选取$sum$的所有$1$对应的基最优。

时间复杂度$O(n\log x)$。

#include
#include
#include
#include
using namespace std;
typedef long long ll;
int Case,n,i,j;ll ans,sum,A,B,a[100],x,v[111111],pool[100];
const int N=20;
ll cal(){
	ll ans=sum;
	for(int S=0;S>i&1)A^=v[i],B^=v[i];
		A-=B;
		if(Ai&1);
	puts("");
}
ll myabs(ll x){return x>0?x:-x;}
ll solve1(int x){
	ll cur=a[x];
	for(int i=x-1;~i;i--)if(sum>>i&1){
		cur^=a[i];
	}
	return myabs(cur-(sum^cur));
}
ll solve2(int x){
	ll cur=0;
	for(int i=x-1;~i;i--){
		cur=max(cur,cur^a[i]);
	}
	return myabs(cur-(sum^cur));
}
int main(){
	//srand(time(NULL));
	scanf("%d",&Case);
	while(Case--){
		scanf("%d",&n);
		//n=rand()%10+1;
		sum=0;
		for(i=0;i>j&1){
				if(a[j])x^=a[j];
				else {a[j]=x;break;}
			}
		}
		
		//ll vio=cal();
		
		for(i=0;i>i&1)a[j]^=a[i];
		
		for(i=60;~i;i--)if(sum>>i&1)break;
		int lim=i;
		if(lim>=0){
			for(i=0;i>j&1){
					if(a[j])x^=a[j];
					else {a[j]=x;break;}
				}
			}
			for(i=0;i>i&1)a[j]^=a[i];
			ans=min(sum,min(solve1(lim),solve2(lim)));
		}else{
			ans=0;
		}
		
		/*A=sum,B=0;*/
		
		//print(sum);
		//for(i=60;~i;i--)if(a[i])print(a[i]);
		
		/*ans=sum;
		for(i=60;~i;i--)if((A^a[i])>=(B^a[i])&&(A^a[i])-(B^a[i])

B. Tribute

按题意模拟即可。

#include
using namespace std;
int casenum, casei;
typedef unsigned int UI;
int n;
vectorvt, wt;
multisetsot;
multisetans;
bool solve()
{
	for(int i = 1; i

C. Boardroom Meeting

CDQ分治+扫描线树状数组，时间复杂度$O(n\log^2n)$。

#include
#include
using namespace std;
const int N=200010;
int Case,n,i,a[N],b[N],c[N],ans,f[N],qa[N],qb[N],bit[N],vis[N],T;
inline void up(int&a,int b){a1,i,j,ca=0,cb=0;
	solve(l,mid);
	for(i=l;i

D. Secret Santa

第二类斯特林数容斥，时间复杂度$O(a\log n)$。

#include
const int N=2010,P=1000000007;
int n,a,i,j,Case,fac[N],S[N][N];
int po(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)t=1LL*t*a%P;return t;}
int T(int m,int n){
  int ans=0;
  for(int k=0;k=1&&j==0){S[i][j]=0;continue;}
    if(i==j){S[i][j]=1;continue;}
    if(j>=1&&j

E. Guessing Game

状压DP，设$f[S]$表示$S$情况下最优策略最坏需要的步数，其中$S$是个$k$位$3$进制数，分别表示每一位未询问、已询问且回答为$0$、已询问且回答为$1$的情况。

用高维前缀和预处理出所有$f[S]=0$的状态，剩下的状态枚举询问哪一位转移即可。

时间复杂度$O(3^kk)$。

#include
#include
using namespace std;
const int N=13,M=1600000;
int p[20],Case,n,m,i,j,k,f[M],c[M];char s[20];
inline int get(int x,int y){return x/p[y]%3;}
int main(){
	for(p[0]=i=1;i

F. Flat Earth

按题意模拟即可。

#include
#include

int casenum, casei, a[10];
const double PI = acos(-1.0);

int main()
{
	scanf("%d", &casenum);
	for(casei = 1; casei

G. We Need More Managers!

建立一张$2^n$个点的图，分别表示每种串。对于每个点，向恰好改变了一位的$n$个点连边。

则题意可转化为对给定$m$个点求出两两最短路作为权值的最小生成树。

设$p_x$和$d_x$分别表示离每个点最近的给定串以及对应的距离，可以BFS求出，则对于一条边$(u,v)$，在生成树中加入一条连接$p_u$和$p_v$，权值为$d_u+d_v+1$的边即可。

时间复杂度$O(n2^n\alpha(m))$。

#include
#include
using namespace std;
const int N=1100000;
int Case,n,m,all,i,j,a[N];char s[100];
int h,t,d[N],p[N],x,y,z,q[N];
int f[N],ans,ce;
struct E{
	int x,y,z;
	E(){}
	E(int _x,int _y,int _z){x=_x,y=_y,z=_z;}
}e[N*20];
inline bool cmp(const E&a,const E&b){return a.z

H. Masterpiece

若不考虑每个点是被第几次走过的，则方案唯一，$O(n)$模拟求出方案后统计分岔点个数$t$，则答案为$2^t$。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
void fre() {  }
#define MS(x, y) memset(x, y, sizeof(x))
#define rt 1,1,n
#define ls o>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template inline void gmin(T1 &a, T2 b) { if (b inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n;
int r[N], c[N];
//try go to (y, x)
bool flag = 1;
int r1, r2;
int c1, c2;
bool doit(int y, int x)
{
    if(r1 == r2 && c1 == c2)return flag = 1;
    if(y > n || x > n)return 0;
    if(!r[y] || ! c[x])return 0;
    --r[y];
    --c[x];
    return flag = 1;
}
int solve()
{
    int ans = 1;
    r1 = 1, c1 = 1;
    r2 = 1, c2 = 1;
    doit(1, 1); --r[1]; --c[1];
    while(1)
    {
        flag = 0;
        if(r1 == r2 && c1 == c2)
        {
            if(r1 == n && c1 == n)
            {
                return ans;
            }
            int rnum = r[r1];
            int cnum = c[c1];
            if(rnum && cnum)
            {
                ans = ans * 2 % Z;
                for(int i = 1; i

I. Don’t Split The Atom!

胜负只取决于$n$的奇偶性。

#include
#include

int casenum, casei, a[10];
const double PI = acos(-1.0);

int main()
{
	scanf("%d", &casenum);
	for(casei = 1; casei

J. Bobby Tables

组合数可以看作长度为$k$的一个区间除以长度为$k$的一个前缀。

枚举每个$k$作为前缀，二分对应的区间，取对数加速判定，在附近配合取模判定即可。

时间复杂度$O(m\log m)$。

#include
#include
#include
using namespace std;
typedef long double ld;
const int N=200010,P=1000000007,K=20;
const ld eps=1e-2;
int Case,n,m,i,a[N],fac[N],inv[N],mul;
ld Log[N],s[N],sum;
inline bool check(int n,int m){
	ld A=s[n]-s[n-m]-s[m];
	if(fabs(A-sum)>eps)return 0;
	int B=1LL*fac[n]*inv[n-m]%P*inv[m]%P;
	if(B!=mul)return 0;
	puts("YES");
	printf("%d %d\n",n,m);
	return 1;
}
inline void solve(){
	scanf("%d%d",&n,&m);
	sum=0;
	mul=1;
	for(i=1;i=i
		//1>1;
			ld A=s[mid+i-1]-s[mid-1]-s[i];
			if(fabs(A-sum)

K. Triples

长链剖分或树分治经典题。

#include
#include
#include
#include
#define pb push_back
#define V vector
#define N 200010
using namespace std;
typedef long long ll;
typedef pairP;
int Case;
int n,i,x,y,g[N],v[Nh[N];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline bool cmp(V*a,V*b){return a->size()>b->size();}
templateinline C&get(V&a,size_t x){return a[a.size()-x-1];}
V*dfs(int x,int y){
  V*>t;
  for(int i=g[x];i;i=nxt[i])if(v[i]!=y)t.pb(dfs(v[i],x));
  if(!t.size())return new V(1,1);
  sort(t.begin(),t.end(),cmp);
  V*a=t[0];
  a->pb(1);
  if(t.size()==1)return a;
  Vb;
  b.resize(t[1]->size()+1,0);
  for(int i=1;i*u=t[i];
    for(int j=1;jsize();j++){
      int ch=get(*u,j-1),&rt=get(*a,j);ll&rd=get(b,j);
      ans+=1LL*ch*rd;
      rd+=1LL*ch*rt;
      rt+=ch;
    }
  }
  for(int i=1;in){
      y=x,x=v[i],t=1;
      break;
    }
  }while(t);
  return x;
}
inline void work(V >&d,V >&q,int k,bool rt,int x){
  int st=k==1?0:d.size()-1,en=k==1?d.size():-1;Va(1,rt); 
  for(int i=st;i!=en;i+=k){
    VD=d[i];
    for(V::iterator p=q[i].begin();p!=q[i].end();p++){
      int j=p->first;
      if(jsecond;
    }
    a.resize(max(a.size(),D.size()),0);
    for(int j=0;j::iterator p=h[x].begin();pfirst;
    if(jsecond;
  }
}
void dfsd(int x,int y,int z,V&d){
  if(z==d.size())d.pb(1);else d[z]++;
  for(int i=g[x];i;i=nxt[i])if(v[i]!=y&&!del[v[i]])dfsd(v[i],x,z+1,d);
}
void dfsq(int x,int y,int z,V
&q){
  for(V
::iterator i=h[x].begin();ifirst-z;
    if(t>=0)q.pb(P(t,i->second));
  }
  for(int i=g[x];i;i=nxt[i])if(v[i]!=y&&!del[v[i]])dfsq(v[i],x,z+1,q);
}
void solve(int x){
  int y=findroot(x);
  del[y]=1;
  for(int i=g[y];i;i=nxt[i])if(!del[v[i]])solve(v[i]);
  V >d;V >q;
  for(int i=g[y];i;i=nxt[i])if(!del[v[i]]){
    VA(1,0);
    dfsd(v[i],-1,1,A);
    d.pb(A);
    V
B;
    dfsq(v[i],-1,1,B);
    q.pb(B);
  }
  work(d,q,1,1,y),work(d,q,-1,0,y);
  del[y]=0;
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    i=x=y=0;
    memset(g,0,sizeof g);
    memset(f,0,sizeof f);
    memset(v,0,sizeof v);
    memset(nxt,0,sizeof nxt);
    ed=0;
    memset(del,0,sizeof del);
    ans=0;
    for(i=0;i

L. Related Languages

枚举$O(nm)$对区间右端点，左端点的取值满足单调性，双指针即可。

时间复杂度$O(nm)$。

#include
const int N=4010;
int Case,n,m,i,j,k,ans,g[N*3];
char a[N],b[N],f[N][N];
int w[N*3],V;
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d%d%s%s",&n,&m,&V,a+1,b+1);
    ans=0;
    for(i=1;i0&&W>V){
        G--;
        W-=f[i-G][j-G];
      }
      g[k]=G;
      w[k]=W;
      if(G>ans)ans=G;
    }
    printf("%d\n",ans);
  }
}

上一篇：es分布式文档系统_bulk api的奇特json格式与底层性能优化关系

下一篇：Winform中TextBox控件开启自动提示补全功能

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Petrozavodsk Winter-2018. Jagiellonian U Contest
文章链接：http://soscw.com/index.php/essay/53738.html

亲，登录后才可以留言！

Petrozavodsk Winter-2018. Jagiellonian U Contest

评论

热门文章

推荐文章

最新文章

置顶文章