POI2010

orz hhw posted @ 2017年11月22日 22:43 in 做题记录 with tags 解题报告 POI , 162 阅读

T1.Guilds 并查集判断有没有孤立点即可

#include<cstdio>
#define N 200100
int n,m,i,x,y,p,q,fa[N],sz[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void uni(int x,int y){
	p=find(x);q=find(y);
	if(sz[p]>sz[q])p^=q^=p^=q;
	sz[q]+=sz[p];fa[p]=q;
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)fa[i]=i,sz[i]=1;
	for(i=1;i<=m;i++)scanf("%d%d",&x,&y),uni(x,y);
	for(i=1;i<=n;i++)if(sz[i]==1&&fa[i]==i)return puts("NIE"),0;
	puts("TAK");
}

T2.Railway(未完成) 这题是双栈排序的加强版,不过我连双栈排序都没做过,就先把双栈排序做了

#include<cstdio>
#include<algorithm>
#define N 1111
#define M 2222222
using namespace std;
int n,i,j,tot,tp1,tp2,now,col[N],mi[N],a[N],fir[N],la[M],ne[M],st1[N],st2[N];bool flag;
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int co){
	col[x]=co;
	for(int i=fir[x];i;i=ne[i])if(!col[la[i]])dfs(la[i],3-co);else if(col[la[i]]==col[x])flag=1;
}
int main(){
	scanf("%d",&n);flag=0;
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(mi[n]=a[n],i=n-1;i>=1;i--)mi[i]=min(mi[i+1],a[i]);
	for(i=1;i<n;i++)for(j=i+1;j<n;j++)if(mi[j+1]<a[i]&&a[i]<a[j])ins(i,j),ins(j,i);
	for(i=1;i<=n;i++)if(!col[i])dfs(i,1);
	if(flag)return puts("0"),0;
	for(now=1,i=1;i<=n;i++){
		if(col[i]==1)st1[++tp1]=a[i],printf("a ");else st2[++tp2]=a[i],printf("c ");
		for(;(tp1&&st1[tp1]==now)||(tp2&&st2[tp2]==now);now++){
			if(tp1&&st1[tp1]==now)tp1--,printf("b");
			if(tp2&&st2[tp2]==now)tp2--,printf("d");
			if(now!=n)printf(" ");
		}
	}
}

可以考虑维护每个点的前向边和后向边,前向边还是比较好维护的,线段树搞搞就可以啦,后向边挺难写的,要线段树上挂链。。贴个标程算了

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
const int MAXN=100057;
const int INF=1000000000;
int poc[MAXN],rev[MAXN],mini[MAXN],c[MAXN];
int n;
vector<int> tab[MAXN];
bool niet=false;
struct Drzewo {
	Drzewo* left;
    Drzewo* right;
	int key;
	int dist;
};

inline Drzewo* create(int x) {
	Drzewo* d = new Drzewo;
	d->key   = x;
	d->dist  = 1;
	d->left  = NULL;
	d->right = NULL;

	return d;
}

inline int top(Drzewo* d) {
	return (d==NULL)?(0):(d->key);
}

inline int dist(Drzewo* d){
	return (d==NULL)?(0):(d->dist);
}

Drzewo* merge(Drzewo* a, Drzewo* b) {
	if (a==NULL) return b;
	if (b==NULL) return a;
	// a!=NULL && b!=null
	if (top(b)<top(a)) swap(a,b);
	a->left = merge(a->left,b);
	if (dist(a->left) > dist(a->right) ) swap(a->right,a->left);
	if (a->right==NULL) a->dist = 0; else a->dist = 1+a->right->dist;
	return a;
}

Drzewo* deleteMin(Drzewo* d) {
	if (d!=NULL) {
		Drzewo* tmp = merge(d->left,d->right);
		free(d);
		return tmp;
	}
	return NULL;
}

inline bool isEmpty(Drzewo* d) {
	return (d==NULL);
}

void paint(int p,int colour) {
	c[p]=colour;
	for(int i=0;i<(int)tab[p].size();i++) {
		if (c[tab[p][i]]==0) paint(tab[p][i],colour%2+1); else
		if (c[tab[p][i]]!=(colour%2+1)) niet=true;
	}
}

bool checkOut() {
	stack<int> st[2];
	for(int i=0;i<2;i++) st[i].push(-1);
	int passed = 1;
	for(int i=1;i<=n;i++) {
		if (c[i]!=0) st[c[i]-1].push(poc[i]); else return false;
		bool change = true;
		while (change) {
			change = false;
			for(int j=0;j<2;j++) {
				while (st[j].top()==passed) {
					passed++;
					st[j].pop();
					change = true;
				}
			}
		}
	}
	return (passed==n+1);
}

int main() {
	Drzewo* stos[MAXN]; 
	int head = -1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&poc[i]);
		rev[poc[i]]=i;
	}
	int prev=INF;
	for(int i=n;i>=1;i--) {
		mini[i]=prev;
		prev=min(prev,poc[i]);
	}
	for(int i=1;i<=n;i++) {
		int d=poc[i], e=mini[i];
		Drzewo* tmp = create(poc[i]);
		bool finished = false;
		while (head!=-1 && !finished) {
			Drzewo* v=stos[head];
			int val=top(v); 
			if (val<d) {
				tab[i].push_back(rev[val]);
				tab[rev[val]].push_back(i);
				tmp=merge(tmp,v);
				head--;
			} else finished = true;
		}
		finished = false;
		head++; stos[head]=tmp;
		while (head!=-1 && !finished) {
			tmp=stos[head]; head--;
			while (!isEmpty(tmp) && (top(tmp)<e)) tmp=deleteMin(tmp);
			
			if (!isEmpty(tmp)) {
				head++; stos[head] = tmp;
				finished = true;
			}
		}
	}
	for(int i=1;i<=n;i++) c[i]=0;
	for(int i=1;i<=n;i++) if (c[i]==0)  paint(i,1);
	niet = checkOut();
	if (!niet) printf("NIE\n"); else {
		printf("TAK\n");
		for(int i=1;i<=n;i++) printf("%d ",c[i]);
		printf("\n");
	}
}

T3 Beads 这种题目是常规字符串算法无法胜任的,要用HASH大法,两边各统计哈希值前缀和,然后求的时候从$1$到$n$暴力求,求的复杂度$O(1)$,要求$\sum_{i=1}^n\frac{n}{i}$次,也就是$nlgn$次,然后再排序去重,复杂度$O(nlg^2n)$

#include<cstdio>
#include<algorithm>
typedef unsigned long long LL;
#define S 999983LL
#define N 1111111
using namespace std;
int n,i,j,top,cnt,ans,tp,q[N];
LL w,a[N],s1[N],s2[N],st[N];
int main(){
	scanf("%d",&n);w=1;
	for(i=1;i<=n;i++)scanf("%llu",&a[i]),s1[i]=s1[i-1]*S+a[i];
	for(i=n;i;i--)s2[i]=s2[i+1]*S+a[i];
	for(i=1;i<=n;i++){
		top=0;w=w*S;
		for(j=1;j+i-1<=n;j+=i)st[++top]=min(s1[j+i-1]-s1[j-1]*w,s2[j]-s2[j+i]*w);
		sort(st+1,st+top+1);cnt=unique(st+1,st+top+1)-(st+1);
		if(cnt>ans)ans=cnt,q[tp=1]=i;else if(ans==cnt)q[++tp]=i;
	}
	printf("%d %d\n",ans,tp);
	for(i=1;i<=tp;i++)if(i==tp)printf("%d",q[i]);else printf("%d ",q[i]);
}

T4 Divine divisor 首先Miller-Rabin算法的基础是费马小定理,大概就是n是一个奇素数,$1\leq a<n,a^{n-1}\ mod\ n=1$

可以用这个定理为基础进行Miller-Rabin判断一个大于等于3的数n是否为质数,然后进行T次如下操作:

随机选择一个整数a(2≤a≤n-2),计算y=a^r mod n,然后如果y^(n-1) mod n=1则不是负数,否则继续判断,若T次结束就是素数

这题大概就是弄出$10^6$以内的素数,然后剩下的数只可能是$p$,$p^2$或$pq$,把$p$和$p^2$搞出来后互相gcd,然后剩下的要不然是素数要不然是不同的素数相乘,统计一下答案就可以了。。不过挺难弄的,不想搞了。。大概后面有几个点错了、、一开始是米勒罗宾写炸没快速乘。。改了也WA。。

然后改了一下写的姿势还是WA,和正确的程序对比下发现Millar-Rabin是错的。。看来4行的米勒罗宾是不靠谱的,就拉了个正常的米勒罗宾,然后就过了。。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define N 1111111
using namespace std;
typedef long long LL;
int i,j,n,w,now,res,ans,cnt,ww,prime[N],c[N];
LL g,z[N],W[]={0,2,3,11,67};bool f[N];
struct BI{
	int a[500],h;
	BI operator +(const BI &x)const{
    	BI ret;int p=0;
    	memset(ret.a,0,sizeof(ret.a));
    	for(int i=1;i<=h;i++){
    		ret.a[i]=a[i]+x.a[i]+p;
      		p=ret.a[i]/10;
      		ret.a[i]=ret.a[i]%10;
    	}
    	ret.h=h;if(p>0)ret.a[++ret.h]=p;
    	return ret;
  }
}ANS;
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
LL mul(LL a,LL b,LL M){
	LL ans=0;
	for(;b;b>>=1){
		if(b&1)ans=(ans+a)%M;
		a=(a+a)%M;
	}
	return ans;
}
LL pow(LL a,LL b,LL M){
	LL ans=1;
	for(;b;b>>=1){
		if(b&1)ans=mul(ans,a,M);
		a=mul(a,a,M);
	}
	return ans;
}
bool mr(LL n){
    if (n<2)return 0;if (n==2)return 1;if (!(n&1))return 0;
    LL d=n-1,r=0;
    while(!(d&1))r++,d>>=1;
    for (int a=1;a<=4;a++){
        LL now=W[a];if(now==n)continue;
        LL v=pow(now,d,n);if(v==1||v==n-1)continue;
        bool find=0;
        for(int b=1;b<r&&!find;b++){
            v=mul(v,v,n);
            if(v==n-1)find=1;
        }
        if(!find)return 0;
    }
    return 1;
}
void ql(){cnt++;for(int k=1;k<=n;k++)while(z[k]%g==0)z[k]/=g,c[cnt]++;}
int main(){
	for(w=1000000,i=2;i<=w;i++){
		if(!f[i])prime[++cnt]=i;
		for(j=1;j<=cnt&&i*prime[j]<=w;j++){
			f[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%lld",&z[i]);
		for(j=1;j<=cnt;j++)while(z[i]%(LL)prime[j]==0)c[j]++,z[i]/=(LL)prime[j];
	}
	for(i=1;i<n;i++)
		for(j=i+1;j<=n;j++)
			if(z[i]!=1&&z[j]!=1&&z[i]!=z[j]){
				g=gcd(z[i],z[j]);
				if(g!=1){
					ql();
					if(z[i]!=1)g=z[i],ql();
					if(z[j]!=1)g=z[j],ql();
				}
			}
	for(i=1;i<=n;i++)if(z[i]!=1){
		g=ceil((LL)sqrt(z[i]));
		if(g*g==z[i])ql();
	}
	for(i=1;i<=n;i++)if(mr(z[i]))g=z[i],ql(),ww++;
	for(i=1;i<=cnt;i++)if(c[i]>ans)ans=c[i],res=1;else if(c[i]==ans)res++;
	for(i=1;i<=n;i++)if(z[i]!=1){
		now=0;
		for(j=i;j<=n;j++)if(z[j]==z[i])now++;
		if(now>ans)ans=now,res=1;else if(now==ans)res+=2;
	}
	printf("%d\n",ans);
  	for(ANS.h=1,ANS.a[1]=1,i=0;i<res;i++)ANS=ANS+ANS;
	for(ANS.a[1]--,i=ANS.h;i;i--)printf("%d",ANS.a[i]);
}

T5 Intelligence test 写了个set结果T了,然后卡了卡常又T了,然后加了个读入优化才卡过

#include<cstdio>
#include<set>
using namespace std;
int T,n,i,x,m,pos;bool flag;char ch;
set<int> st[1000011];
void read(int &x){
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
}
int main(){
	read(n);
	for(i=1;i<=n;i++){
		read(x);
		st[x].insert(i);
	}
	read(T);
	while(T--){
		read(m);
		pos=0;flag=0;
		for(i=1;i<=m;i++){
			read(x);
			if(!flag)if(st[x].size()==0){flag=1;}
			else if(*--st[x].end()<=pos){flag=1;}
			else pos=*st[x].upper_bound(pos);
		}
		if(!flag)puts("TAK");else puts("NIE");
	}
}

T6 Antisymmetry 把Manacher的判断条件稍微改一下就可以了,顺便把Manacher背了一下,差不多背会了,不过交的时候没有注意奇数长度的是不合法的WA了一发

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500010
using namespace std;
typedef long long LL;
LL ans;int n,i,l,mx,p,r[N*2],ma[N*2];char s[N];
int main(){
	scanf("%d%s",&n,s);
	ma[l++]=7;ma[l++]=3;for(i=0;i<n;i++)ma[l++]=2*(s[i]-'0'+1),ma[l++]=3;
	for(i=1;i<l;i+=2){
		r[i]=mx>i?min(r[2*p-i],mx-i):1;
		for(;ma[i+r[i]]+ma[i-r[i]]==6;r[i]++);
		if(i+r[i]>mx)mx=i+r[i],p=i;
	}
	for(i=3;i<l;i+=2)ans+=(LL)(r[i]-1)/2;
	printf("%lld",ans);
}

T7 Hamsters 首先可以求出每两个串的最长后缀接前缀,这可以用HASH完成,这样$dis[i][j]=len[j]-cal(i,j)$,注意自己接自己的时候不能$cal(i,j)$不能为$len[j]$,然后可以通过类似Floyd+快速幂的方法快速求解,时间复杂度$O(kn+n^3lgm)$,学会了动态开数组的新姿势

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
typedef unsigned long long LL;
#define N 203
#define M 100100
#define S 999983LL
using namespace std;
int n,m,i,j,k,len[N];
LL miv,*h1[N],pow[M],f[N][N],g[N][N],ans[N][N];char s[M];
int cal(int x,int y){
	for(int i=min(len[x],len[y])-(len[y]<=len[x]);i;i--)if(h1[x][len[x]]-h1[x][len[x]-i]*pow[i]==h1[y][i])return i;
	return 0;
}
int main(){
	scanf("%d%d",&n,&m);miv=1e18;
	for(i=1;i<=n;i++){
		scanf("%s",s+1);len[i]=strlen(s+1);
		h1[i]=new LL[len[i]+1];h1[i][0]=0;
		for(j=1;j<=len[i];j++)h1[i][j]=h1[i][j-1]*S+(LL)(s[j]-'a'+1);
	}
	for(pow[0]=1,i=1;i<=100000;i++)pow[i]=pow[i-1]*S;
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=len[j]-cal(i,j);
	memset(ans,0x3f,sizeof ans);m--;
	for(i=1;i<=n;i++)ans[i][i]=0;
	for(;m;m>>=1){
		if(m&1){
			memset(g,0x3f,sizeof g);
			for(k=1;k<=n;k++)
				for(i=1;i<=n;i++)
					for(j=1;j<=n;j++)
						g[i][j]=min(g[i][j],ans[i][k]+f[k][j]);
			for(i=1;i<=n;i++)for(j=1;j<=n;j++)ans[i][j]=g[i][j];
		}
		memset(g,0x3f,sizeof g);
		for(k=1;k<=n;k++)
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
					g[i][j]=min(g[i][j],f[i][k]+f[k][j]);
		for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=g[i][j];
	}
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)miv=min(miv,ans[i][j]+len[i]);
	printf("%llu",miv);
}

T8 Blocks 首先如果一个区间的平均值大于k即是合法的,对于每个$k$我们要求出这个最大的区间,可以用$sum[i]=sum[i-1]+a[i]-k$,这样维护一个单调下降的sum单调栈,就可以在$O(n)$的时间内求出答案

#include<cstdio>
#include<algorithm>
#define N 1111111
using namespace std;
int n,m,i,k,top,ans,q[N];
long long a[N],sum[N];
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]);
	while(m--){
		top=ans=0;scanf("%d",&k);
		for(i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]-k;
		for(i=1;i<=n;i++)if(sum[q[top]]>sum[i])q[++top]=i;
		for(i=n;i;i--){
			for(;top&&sum[i]>=sum[q[top-1]];top--);
			ans=max(ans,i-q[top]);
		}
		!m?printf("%d",ans):printf("%d ",ans);
	}
}

T9 Sheep 首先如果一条对角线两边的羊都是偶数就是合法的,但如果暴力判断很明显会超时,可以以每个牧场边上的点为极点进行极角排序,然后就可以判断每条对角线是否合法了,接下来只要一个简单的区间DP就行啦,时间复杂度$O(nmlgm+n^3)$

#include<cstdio>
#include<algorithm>
#define N 620
#define M 20020
using namespace std;
int n,k,m,i,j,l,p,MO,f[N][N];bool v[N][N],ok;
struct EG{int x,y;}eg[M],q[N],st;
int multi(EG a,EG b,EG c){return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}
bool cmp(EG a,EG b){return multi(st,a,b)<0;}
int main(){
	scanf("%d%d%d",&n,&m,&MO);
	for(i=1;i<=n;i++)scanf("%d%d",&q[i].x,&q[i].y);
	for(i=1;i<=m;i++)scanf("%d%d",&eg[i].x,&eg[i].y);
	for(i=1;i<=n;i++){
		st=q[i];sort(eg+1,eg+m+1,cmp);
		for(k=1,j=i%n+1,ok=1;k<=m;ok=!ok,k++)
			for(;i!=j&&(p=multi(st,q[j],eg[k]))<=0;j=j%n+1)if(p<0)v[i][j]=ok;
		for(;i!=j;j=j%n+1)v[i][j]=ok;
	}
	for(i=1;i<=n;i++)f[i][i%n+1]=1;
	for(l=2;l<=n;l++)
		for(i=1;i<=n;i++){
			j=(i+l-1)%n+1;
			for(k=1;k<=n;k++)if(v[i][k]&&v[k][j])f[i][j]=(f[i][j]+f[i][k]*f[k][j])%MO;
		}
	printf("%d",f[1][n]);
}

T10 Teleportation 首先很明显这是一个分层的图,每一层内互相连,然后层之间互相连,于是这个图最多只有四层

为了方便,先把和1相连的点放到第一层中,把和2相连的点放到第二层中,然后可以证明把剩下的点放到第一层或第二层不是好的选择,因为如果不放可以和他们的点全连,而且自己也可以连

剩下的点如果和第一层的点连过,就和所有第一层的点连,如果和第二层的点连过,就和所有第二层的点连,然后全部互相连,这样就能得到最优的答案啦

#include<cstdio>
#include<algorithm>
#define N 40040
#define M 1001000
using namespace std;
int n,m,i,a[M],b[M],f[N];bool f1[N],f2[N];long long ans,s1,s2,s3;
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=m;i++){
		scanf("%d%d",&a[i],&b[i]);
		if(a[i]<=2)f[b[i]]=a[i];
		if(b[i]<=2)f[a[i]]=b[i];
	}
	for(i=3;i<=n;i++)if(!f[i])s3++;else if(f[i]==1)s1++;else s2++;
	for(ans=(s3*(s3-1)+s1*(s1+1)+s2*(s2+1))/2,i=1;i<=m;i++){
		if(f[a[i]])if(f[a[i]]==1)f1[b[i]]=1;else f2[b[i]]=1;
		if(f[b[i]])if(f[b[i]]==1)f1[a[i]]=1;else f2[a[i]]=1;
	}
	for(i=3;i<=n;i++)if(!f[i])if(f1[i])ans+=s1;else if(f2[i])ans+=s2;else ans+=max(s1,s2);
	printf("%lld",ans-m);
}

T11 Monotonicity(双倍) 要用线段树维护DP,有点贪心的思想,不管符号的限制,每次尽量取最优的,不知道为何这样是对的。。

#include<cstdio>
#include<algorithm>
#define N 500100
using namespace std;
int n,k,w,i,ans,c,p[N],a[N],r[N],xd[N*2];
char s[3],ch;
struct XD{
	struct T{int l,r,mv;}t[N*8];
	void build(int k,int l,int r){
		t[k].l=l;t[k].r=r;
		if(l==r)return;
		int mid=(l+r)>>1;
		build(k<<1,l,mid);build(k<<1|1,mid+1,r);
	}
	void ins(int k,int x,int z){
		int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
		t[k].mv=max(t[k].mv,z);
		if(l==r)return;
		if(x<=mid)ins(k<<1,x,z);else ins(k<<1|1,x,z);
	}
	int find(int k,int x,int y){
		if(x>y)return 0;
		int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
		if(x<=l&&r<=y)return t[k].mv;
		if(x>mid)return find(k<<1|1,x,y);
		else if(y<=mid)return find(k<<1,x,y);
		else return max(find(k<<1,x,mid),find(k<<1|1,mid+1,y));
	}
}dw,up;
void read(int &x){
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
}
int main(){
	read(n);read(k);w=1000000;
	for(i=1;i<=n;i++)read(a[i]);
	dw.build(1,1,w);up.build(1,1,w);
	for(i=0;i<k;i++){
		scanf("%s",s);
		if(s[0]=='<')p[i]=1;else if(s[0]=='>')p[i]=2;else p[i]=3;
	}
	for(i=1;i<=n;i++){
		r[i]=1+max(xd[a[i]],max(dw.find(1,1,a[i]-1),up.find(1,a[i]+1,w)));
		ans=max(r[i],ans);c=p[(r[i]-1)%k];
		if(c==1)dw.ins(1,a[i],r[i]);else if(c==2)up.ins(1,a[i],r[i]);else xd[a[i]]=r[i];
	}
	printf("%d",ans);
}

T12 The Minima Game $dp[i]$表示在$i$先手比后手多取的值,$dp[i]=max(a[j+1]-dp[j])$,单调维护$a[j+1]-dp[j]$的值即可

#include<cstdio>
#include<algorithm>
#define N 1111111
using namespace std;
int n,i;long long ma,a[N],dp[N];
int main(){
	scanf("%d",&n);for(i=1;i<=n;i++)scanf("%lld",&a[i]);sort(a+1,a+n+1);
	for(ma=a[1],i=1;i<=n;i++)dp[i]=ma,ma=max(ma,a[i+1]-dp[i]);
	printf("%lld",dp[n]);
}

T13 翻译都没有一定很难

T14 Frogs 由于第0-k近的点范围是单调增的,找第$k$近点就可以$O(n)$维护,然后就可以求出后一步走到的点,可这题如果直接倍增会MLE我也是醉了,然后压一下还是TLE也没办法。。然后必须用类似快速幂的方法做到$O(n)$的空间,没读入优化9.5S卡过

#include<cstdio>
#define N 1000100
typedef long long LL;int n,k,i,j,l,r,pos,ne[N][61];LL m,a[N];
int main(){
	scanf("%d%d%lld",&n,&k,&m);for(i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(l=1,r=k+1,ne[1][0]=k+1,i=2;i<=n;i++){
		for(;r<n&&a[r+1]-a[i]<a[i]-a[l];l++,r++);
		ne[i][0]=a[r]-a[i]>a[i]-a[l]?r:l;
	}
	for(j=1;j<=60;j++)for(i=1;i<=n;i++)ne[i][j]=ne[ne[i][j-1]][j-1];
	for(i=1;i<=n;i==n?printf("%d",pos):printf("%d ",pos),i++)for(pos=i,j=0;j<=60;j++)if(m&(1LL<<j))pos=ne[pos][j];
}
#include<cstdio>
#define N 1000100
typedef long long LL;int n,k,i,j,l,r,pos,ne[N],f[N],g[N],t[N];LL m,a[N];
int main(){
	scanf("%d%d%lld",&n,&k,&m);for(i=1;i<=n;i++)scanf("%lld",&a[i]),g[i]=i;
	for(l=1,r=f[1]=k+1,i=2;i<=n;i++){
		for(;r<n&&a[r+1]-a[i]<a[i]-a[l];l++,r++);
		f[i]=a[r]-a[i]>a[i]-a[l]?r:l;
	}
	for(;m;m>>=1){
		if(m&1){
			for(i=1;i<=n;i++)t[i]=f[g[i]];
			for(i=1;i<=n;i++)g[i]=t[i];
		}
		for(i=1;i<=n;i++)t[i]=f[f[i]];
		for(i=1;i<=n;i++)f[i]=t[i];
	}
	for(i=1;i<=n;i++)printf("%d%c",g[i],i==n?'\n':' ');	
}

T15 最短5K,蒟蒻无能为力

T16 Bridges 觉得这是一个欧拉回路判定问题,搜了下发现混合图欧拉回路判定需要网络流,首先所有点入度-出度必须是2的倍数,然后对于入不敷出的点连汇点/2,源点入度多的/2,然后对于每条无向边先设好方向,连边流量为1,就可以达到无向边效果,检查是否满流即可,这题再加个二分答案就行了,不过我WA了也不想调了

#include<cstdio>
#include<cstring>
#define CL(a) memset(a,0,sizeof(a))
#define inf 1e9
#define N 2222
#define M 8888
int n,m,i,u,s,t,l,r,mid,now,tot,tmp,flow,ext,ans,a[N],b[N],c[N],d[N],fir[N],dist[N],cur[N],pre[N],numb[N],in[N],va[M],ne[M],la[M];
void ins(int x,int y,int z){
	la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;
	la[++tot]=x;va[tot]=0;ne[tot]=fir[y];fir[y]=tot;
}
int ISAP(){
	CL(numb);CL(dist);CL(pre);
	for(i=1;i<=t;i++)cur[i]=fir[i];u=s;numb[0]=t;
	while(dist[s]<t){
		if(u==t){
			now=inf;
			for(i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<now)now=va[cur[u=i]];
			for(i=s;i!=t;i=la[cur[i]]){
				va[cur[i]]-=now;
				va[cur[i]^1]+=now;
			}
			flow+=now;
		}
		for(i=cur[u];i;i=ne[i])if(va[i]&&dist[la[i]]+1==dist[u])break;
		if(i){
			cur[u]=i;
			pre[la[i]]=u;
			u=la[i];
		}else{
			if(0==--numb[dist[u]])break;
			for(i=cur[u]=fir[u],tmp=t;i;i=ne[i])
				if(dist[la[i]]<tmp&&va[i])tmp=dist[la[i]];
			++numb[dist[u]=tmp+1];
			if(u!=s)u=pre[u];
		}
	}
	return flow;
}
bool ok(int w){
	tot=1;CL(fir);CL(in);CL(va);CL(la);CL(ne);s=n+1;t=s+1;ext=0;
	for(i=1;i<=m;i++){
		if(c[i]<=w&&d[i]<=w)in[a[i]]++,in[b[i]]--,ins(a[i],b[i],1);
		else if(c[i]<=w)in[a[i]]--,in[b[i]]++;
		else if(d[i]<=w)in[b[i]]--,in[a[i]]++;
		else return 0;
	}
	for(i=1;i<=n;i++)if(in[i]&1){return 0;}else if(in[i]>0)ins(s,i,in[i]/2),ext+=in[i]/2;else if(in[i]<0)ins(i,t,(-in[i])/2);
	return ISAP()>=ext;
}
int main(){
	freopen("mos2b.in","r",stdin);freopen("mos.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
	ans=-1;l=0;r=1000;
	while(l<=r){
		mid=l+r>>1;
		if(ok(mid))ans=mid,r=mid-1;else l=mid+1;
	}
	if(ans==-1)puts("NIE");else printf("%d",ans);
}

T17 Pilots 维护两个单调队列即可

#include<cstdio>
#include<algorithm>
#define N 3001000
using namespace std;
int n,k,i,h1,t1,h2,t2,t,ans,a[N],q1[N],q2[N];
int main(){
	scanf("%d%d",&k,&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);
	h1=1;h2=1;t1=0;t2=0;t=1;
	for(i=1;i<=n;i++){
		for(;h1<=t1&&a[i]>=a[q1[t1]];t1--);
		for(;h2<=t2&&a[i]<=a[q2[t2]];t2--);
		q1[++t1]=i;q2[++t2]=i;
		while(a[q1[h1]]-a[q2[h2]]>k)if(q1[h1]<q2[h2])t=q1[h1++]+1;else t=q2[h2++]+1;
		ans=max(ans,i-t+1);
	}
	printf("%d",ans);
}

感觉收获还是挺大的,切这一套题我学会了大素数判定,背会了Manacher,加深了对字符串HASH的理解,学会了使用set的正确姿势,还学会了一些倍增的黑科技,以及混合图欧拉回路的判定