POI2005
T1 Pra-Dextrogyrate camel 把所有点从2号点开始按关于1号点的极角排序，然后用$dp[i][j]$表示从$1$出发走到$j$，最后一条路是$(i,j)$，然后暴力转移是$n^3$的，把所有点关于$i$号点按极角排序，则对于所有转移$f[ax][i]\to f[i][bx]$,$ax$和$bx$都是单调递增的，就可以$n^2$转移了，注意把不合法情况叉掉
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2222
using namespace std;
int n,i,j,t1,t2,h,t,v,ans,dp[N][N],sa[N],sb[N];
struct P{int x,y;}p[N];
int get(P x,P y,P z){return (y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);}
bool cmp(int x,int y){return get(p[i],p[x],p[y])<0;}
int w(int x){return x<0?-1:x>0?1:0;}
bool cmp2(P x,P y){
int a=get(p[1],p[2],x),b=get(p[1],p[2],y);
return (w(a)*w(b)<0)?a<b:get(p[1],x,y)<0;
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
for(memset(dp,-1,sizeof(dp)),sort(p+3,p+n+1,cmp2),dp[1][2]=1,i=2;i<=n;i++){
for(t1=t2=0,j=1;j<i;j++)if(dp[j][i]>-1&&get(p[i],p[j],p[1])>=0)sa[++t1]=j;
for(j=i+1;j<=n;j++)if(get(p[i],p[1],p[j])>=0)sb[++t2]=j;
sort(sa+1,sa+t1+1,cmp);sort(sb+1,sb+t2+1,cmp);
for(h=t=1,v=-1;t<=t2;t++){
for(;h<=t1&&get(p[i],p[sa[h]],p[sb[t]])>0;)v=max(v,dp[sa[h++]][i]);
if(v>-1)dp[i][sb[t]]=max(dp[i][sb[t]],v+1);
}
}
for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)ans=max(ans,dp[i][j]);
printf("%d",ans);
}
T2 Bankomat 写了个set竟然T了QAQ改成vector又MLE了我曰。。MD本地都秒过的，当过了算了
#include<cstdio>
#include<set>
using namespace std;
int n,i,j,a,b,c,d,k,p,ans;char s[1001000];
set<int>st[1010][10];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)for(scanf("%d%s",&k,s+1),j=1;j<=k;j++)st[i][s[j]-'0'].insert(j);
for(a=0;a<=9;a++)for(b=0;b<=9;b++)for(c=0;c<=9;c++)for(d=0;d<=9;d++){
for(i=1;i<=n;i++){
if(!st[i][a].size()||!st[i][b].size()||!st[i][c].size()||!st[i][d].size())break;
p=*st[i][a].begin();
if(*--st[i][b].end()<p)break;p=*st[i][b].lower_bound(p);
if(*--st[i][c].end()<p)break;p=*st[i][c].lower_bound(p);
if(*--st[i][d].end()<p)break;p=*st[i][d].lower_bound(p);
}
if(i>n)ans++;
}
printf("%d",ans);
}
#include<cstdio>
#include<set>
#include<vector>
using namespace std;
int n,i,j,u,a,b,c,d,k,p,ans;char s[1001000];
set<int>st[10];vector<int>to[1010][10];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++){
for(j=0;j<=9;j++)st[j].clear(),to[i][j].push_back(0);
for(scanf("%d%s",&k,s+1),j=1;j<=k;j++)st[s[j]-'0'].insert(j);
for(j=1;j<=k;j++)
for(u=0;u<=9;u++)
if(!st[u].size())to[i][u].push_back(-1);
else if(*--st[u].end()<j)to[i][u].push_back(-1);
else to[i][u].push_back(*st[u].lower_bound(j));
}
for(a=0;a<=9;a++)for(b=0;b<=9;b++)for(c=0;c<=9;c++)for(d=0;d<=9;d++){
for(i=1;i<=n;i++){
p=to[i][a][1];if(p==-1)break;
p=to[i][b][p];if(p==-1)break;
p=to[i][c][p];if(p==-1)break;
p=to[i][d][p];if(p==-1)break;
}
if(i>n)ans++;
}
printf("%d",ans);
}
#include<cstdio>
#include<set>
#include<vector>
using namespace std;
int n,i,j,u,a,b,c,d,A,B,C,D,k,sum,ans[10][10][10][10];char s[1001000];
set<int>st[10];vector<int>to[10];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++){
for(j=0;j<=9;j++)st[j].clear(),to[j].clear();
for(scanf("%d%s",&k,s+1),j=1;j<=k;j++)st[s[j]-'0'].insert(j);
for(j=0;j<=k;j++)
for(u=0;u<=9;u++)
if(!st[u].size())to[u].push_back(-1);
else if(*--st[u].end()<j)to[u].push_back(-1);
else to[u].push_back(*st[u].lower_bound(j));
for(a=0;a<=9;a++){
A=to[a][0];
if(A!=-1)for(b=0;b<=9;b++){
B=to[b][A];
if(B!=-1)for(c=0;c<=9;c++){
C=to[c][B];
if(C!=-1)for(d=0;d<=9;d++){
D=to[d][C];if(D==-1)continue;
ans[a][b][c][d]++;
}
}
}
}
}
for(a=0;a<=9;a++)for(b=0;b<=9;b++)for(c=0;c<=9;c++)for(d=0;d<=9;d++)if(ans[a][b][c][d]==n)sum++;
printf("%d",sum);
}
T3 Pun-point 找出重心，然后转一圈统计出每个角的叉积和点积，然后做一遍字符串的最小表示，再倒着做一遍，就可以判断点集的同构了，但是小数据全过大数据全是NIE，也不知道为什么
#include<cstdio>
#include<algorithm>
#define N 26000
#define eps 1e-9
using namespace std;typedef double LL;
struct P{LL x,y;}p[N],s[N],w[N],q[N];
int n,m,i,j,k,t,T;LL sx,sy;
LL abs(LL x){return x<0?-x:x;}
LL dis(P a,P b){return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);}
P operator-(P a,P b){P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}
LL operator*(P a,P b){return a.x*b.y-a.y*b.x;}
LL operator/(P a,P b){return a.x*b.x+a.y*b.y;}
bool cmp(P a,P b){
LL t=(a-p[1])*(b-p[1]);
if(abs(t)<eps)return dis(a,p[1])<dis(b,p[1]);
return t<0;
}
int Cmp(P a,P b){
if((a.x*b.y-b.x*a.y)<eps)return 0;
if(!a.y)return a.x>0?1:-1;
if(!b.y)return b.x<0?1:-1;
return a.x/a.y>b.x/b.y?1:-1;
}
void kmp(int n){
for(k=0,i=1,j=2;j<=n&&k<=n;){
t=Cmp(s[(i+k-1)%n+1],s[(j+k-1)%n+1]);
t?t>0?i=max(j,i+k+1),j=i+1:j=j+k+1,k=0:k++;
}
}
void get(int n){
for(sx=sy=0,i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y),sx+=p[i].x,sy+=p[i].y,p[i].x*=n,p[i].y*=n;
for(i=1;i<=n;i++)p[i].x-=sx,p[i].y-=sy;
sort(p+2,p+n+1,cmp);
for(p[0]=p[n],p[n+1]=p[1],i=1;i<=n;i++){
s[i].x=(p[i]-p[i-1])*(p[i+1]-p[i]);
s[i].y=(p[i]-p[i-1])/(p[i+1]-p[i]);
}
kmp(n);
for(j=1;j<=n;j++)p[j]=s[(i+j-2)%n+1];
for(i=1,j=n;i<=j;i++,j--)swap(s[i],s[j]);
kmp(n);
for(j=1;j<=n;j++)q[j]=s[(i+j-2)%n+1];
}
int main(){
scanf("%d",&m);get(m);for(i=1;i<=m;i++)w[i]=p[i];
for(scanf("%d",&T);T--;){
scanf("%d",&n);get(n);if(n!=m){puts("NIE");continue;}
for(i=1;i<=n;i++)if(abs(p[i].x*w[i].y-p[i].y*w[i].x)>eps)break;
if(i>n){puts("TAK");continue;}
for(i=1;i<=n;i++)if(abs(w[i].x*q[i].y-w[i].y*q[i].x)>eps)break;
puts(i>n?"TAK":"NIE");
}
}
T4 Toy Cars 贪心挺好想的，每次删掉下个出现最末的就行了，实现看起来也挺简单，不过我怎么想也想不到set这题怎么写，而且可并堆也不太资磁，就用了下priority_queue
#include<cstdio>
#include<queue>
#include<map>
#define N 500100
#define mp make_pair
using namespace std;
priority_queue<pair<int,int> >q;
int m,k,n,i,x,ans,la[N],a[N],ne[N];bool is[N];
int main(){
scanf("%d%d%d",&m,&k,&n);
for(i=1;i<=m;i++)la[i]=n+1;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=n;i;i--)ne[i]=la[a[i]],la[a[i]]=i;
for(i=1;i<=n;i++){
if(is[a[i]]){q.push(mp(ne[i],a[i]));continue;}
if(k){
ans++;q.push(mp(ne[i],a[i]));
is[a[i]]=1;k--;
}else{
while(!is[(q.top()).second])q.pop();
is[q.top().second]=0;q.pop();
ans++;q.push(mp(ne[i],a[i]));
is[a[i]]=1;
}
}
printf("%d",ans);
}
T5 ska Piggy banks 我画了几个图发现不管怎么连只要是一个联通块砸碎一个存钱罐就够了，所以只要判断联通块个数就可以了，一开始写了个没路径压缩的T了，然后改成路径压缩+按秩合并就A了
#include<cstdio>
int n,i,x,p,q,ans,fa[1001000];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)fa[i]=i;
for(i=1;i<=n;i++){
scanf("%d",&x);
p=find(x);q=find(i);
fa[p]=q;
}
for(i=1;i<=n;i++)if(find(i)==i)ans++;
printf("%d",ans);
}
T7 Bank notes 混合背包问题，直接二进制拆分做背包就行了。。C++真是方便，当初写PAS可是超过1K的
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,j,x,w,b[222],dp[20020];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&b[i]);
memset(dp,0x7f,sizeof(dp));dp[0]=0;
for(i=1;i<=n;i++){
scanf("%d",&x);
for(j=0;x>=(1<<j);j++){
x-=(1<<j);
for(w=20000;w>=(1<<j)*b[i];w--)dp[w]=min(dp[w],dp[w-(1<<j)*b[i]]+(1<<j));
}
for(w=20000;w>=x*b[i];w--)dp[w]=min(dp[w],dp[w-x*b[i]]+x);
}
scanf("%d",&w);printf("%d",dp[w]);
}
T8 Dicing 很简单的二分+网络流，二分每个人赢得局数Mid，源点向每个人连mid，每场比赛建点，两个人向比赛连边，比赛向汇点连边判断是否满流即可 有个不到1K的小哥实在是太厉害了，把我碾了
#include<cstdio>
#include<cstring>
#define N 20020
#define M 80080
#define inf 1e9
int n,m,s,t,u,i,x,y,tot,now,tmp,flow,ans,l,r,mid,fir[N],cur[N],pre[N],num[N],d[N],la[M],va[M],ne[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(){
memset(num,0,sizeof(num));memset(d,0,sizeof(d));memset(pre,0,sizeof(pre));
for(i=1;i<=t;i++)cur[i]=fir[i];u=s;num[0]=t;flow=0;
while(d[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]&&d[la[i]]+1==d[u])break;
if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
if(0==--num[d[u]])break;
for(i=cur[u]=fir[u],tmp=t;i;i=ne[i])if(d[la[i]]<tmp&&va[i])tmp=d[la[i]];
++num[d[u]=tmp+1];if(u!=s)u=pre[u];
}
}
return flow;
}
int main(){
scanf("%d%d",&n,&m);s=n+m+1;t=s+1;tot=1;now=1;
for(i=1;i<=n;i++)ins(s,i,1);
for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x,i+n,1),ins(y,i+n,1),ins(i+n,t,1);
for(l=1,r=m;l<=r;){
mid=l+r>>1;
memset(va,0,sizeof(va));
for(i=1;i<=n;i++)va[i*2]=mid,va[i*2+1]=0;
for(i=1;i<=m*3;i++)va[(i+n)*2]=1,va[(i+n)*2+1]=0;
if(ISAP()==m)r=mid-1,ans=mid;else l=mid+1;
}
printf("%d",ans);
}
T9 A Journey to Mars 用拆成一条链，然后用单调队列维护出最右可以到哪个点就可以得到答案，不过要注意正反要各做一遍
#include<cstdio>
#include<set>
#define N 2001000
using namespace std;typedef long long LL;
int n,i,t,res,r[N],q[N],a[N],b[N],sum[N];bool f[N];
void work(int k){
for(i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]-b[i];
for(i=1;i<=n;i++)sum[i+n]=sum[i+n-1]+a[i]-b[i];
for(t=0,sum[2*n+1]=-1e9,i=0;i<=n*2+1;q[++t]=i++)for(;t&&sum[i]<sum[q[t]];r[q[t--]]=i-1);
for(i=0;i<n;i++)if(r[i]-i+1>=n)f[k?n-i:i+1]=1;
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),res+=a[i]-b[i];
if(res<0){for(i=1;i<=n;i++)puts("NIE");return 0;}
work(0);for(i=1;i<=n/2;i++)swap(a[i],a[n-i+1]),swap(b[i],b[n-i+1]);
t=b[1];for(i=1;i<n;i++)b[i]=b[i+1];b[n]=t;
work(1);for(i=1;i<=n;i++)puts(f[i]?"TAK":"NIE");
}
T10 Sum- Fibonacci sums 暴力调整，当$f[i]=3$时,$f[i]=0$,$f[i+2]++,f[i-2]++$；当$f[i]=2$时，如果$f[i-1]=1,f[i]=0,f[i-1]--,f[i+2]++$，否则$f[i+1]++,f[i-2]++$；然后处理进位，可以证明这样调整不会出现反例
#include<cstdio>
#include<algorithm>
using namespace std;
int i,n,m,x,d,f[1001000];
void get(int x){for(;f[x]&&f[x+1];x+=2)f[x]--,f[x+1]--,f[x+2]++;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&f[i]);
for(scanf("%d",&m),n=max(n,m)+3,i=1;i<=m;i++)scanf("%d",&x),f[i]+=x;
for(i=n;i;i--)if(f[i]==3)f[i]=0,f[i+2]++,get(i+2),f[i-2]++,get(i-3);
else if(f[i]==2){
if(f[i-1])f[i]=0,f[i-1]--,f[i+2]++,get(i+2);
else f[i]=0,f[i+1]++,get(i+1),f[i-2]++,get(i-3);
}else get(i-1);
for(f[1]+=f[0];n&&!f[n];n--);
for(printf("%d",n),i=1;i<=n;i++)printf(" %d",f[i]);
}
T11 Template 好神啊，二分+KMP。。
#include<cstdio>
#include<cstring>
#define N 500500
int n,i,k,l,r,mid,cnt,ans,a[N],p[N];char s[N];
bool ok(int x){
int k=p[x];
for(int i=x+1;i<=n;i++){
for(;k&&s[k+1]^s[i];k=p[k]);
if(s[k+1]==s[i])k++;
if(!k)return 0;
if(k==x)k=p[k];
}
return 1;
}
int main(){
scanf("%s",s+1);n=strlen(s+1);
for(i=2;i<=n;i++){
for(;k&&s[k+1]^s[i];k=p[k]);
if(s[k+1]==s[i])k++;
p[i]=k;
}
for(k=n;k;k=p[k])a[++cnt]=k;
for(l=1,r=cnt;l<=r;){
mid=l+r>>1;
if(ok(a[mid]))l=mid+1,ans=mid;else r=mid-1;
}
printf("%d",a[ans]);
}
T12 Akc- Special Forces Manoeuvres 两个圆的并的右端一定是一个点，那么求多个圆的并就可以先算出每两个圆两两相交的右端点的最左边的点，把这个点带进去看看是否在所有圆内就可以了
#include<cstdio>
#include<cmath>
#define N 2022
#define eps 1e-8
#define sqr(x)((x)*(x))
#define dis(a,b)(sqr(x[a]-x[b])+sqr(y[a]-y[b]))
#define up if(mx>ix)mx=ix,my=iy;
#define in(i,vx,vy)(sqr(vx-x[i])+sqr(vy-y[i])<sqr(r[i])+eps)
int n,i,j;double mx,my,ix,iy,jx,jy,ux,uy,s,t,l,x[N],y[N],r[N];
int main(){
for(scanf("%d",&n),i=1;i<=n;i++){
scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
if(i==1)mx=x[i]+r[i],my=y[i];
for(j=1;j<i;j++){
l=dis(i,j);
ix=x[i]+r[i];iy=y[i];if(in(j,ix,iy)){up continue;}
ix=x[j]+r[j];iy=y[j];if(in(i,ix,iy)){up continue;}
if(l<sqr(r[i]+r[j])+eps){
s=((r[i]-r[j])*(r[i]+r[j])/l+1)/2;
t=sqrt(-(l-sqr(r[i]+r[j]))*(l-sqr(r[i]-r[j]))/(l*l*4));
ux=x[j]-x[i],uy=y[j]-y[i];
ix=x[i]+s*ux+t*uy;iy=y[i]+s*uy-t*ux;
jx=x[i]+s*ux-t*uy;jy=y[i]+s*uy+t*ux;
if(ix<jx)ix=jx,iy=jy;
up
}else return printf("%d\n",i),0;
}
for(j=1;j<=i;j++)if(!in(j,mx,my))return printf("%d\n",i),0;
}
puts("NIE");
}
T13 The Bus 直接按照x端点第一关键字y端点第二关键字然后树状数组优化DP就行了
#include<cstdio>
#include<algorithm>
#define N 100100
using namespace std;
int n,m,k,i,j,t,va,ans,tol,cnt1,cnt2,v1[N],v2[N],c[N],f[N];
struct EG{int x,y,z;}eg[N];bool cmp(EG a,EG b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
void ins(int x,int z){for(;x<=cnt2;x+=x&-x)c[x]=max(c[x],z);}
int que(int x){for(ans=0;x;x-=x&-x)ans=max(ans,c[x]);return ans;}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=k;i++)scanf("%d%d%d",&eg[i].x,&eg[i].y,&eg[i].z),v1[i]=eg[i].x,v2[i]=eg[i].y;
sort(v1+1,v1+k+1);sort(v2+1,v2+k+1);cnt1=unique(v1+1,v1+k+1)-(v1+1);cnt2=unique(v2+1,v2+k+1)-(v2+1);
for(i=1;i<=k;i++)eg[i].x=lower_bound(v1+1,v1+cnt1+1,eg[i].x)-v1,eg[i].y=lower_bound(v2+1,v2+cnt2+1,eg[i].y)-v2;
sort(eg+1,eg+k+1,cmp);t=1;
for(i=1;i<=k;i++)f[i]=que(eg[i].y)+eg[i].z,ins(eg[i].y,f[i]),tol=max(tol,f[i]);
printf("%d\n",tol);
}
T15 Dwu-Double-row 考虑到只有处于一个连通块能相互影响，就考虑每个连通块的情况
枚举连通块中的一个点是否改变，那么剩下的是否改变就可以得出，取一个改变代价小的即可
#include<cstdio>
#include<algorithm>
#define N 101000
using namespace std;
int n,i,j,k,x,p,q,ans,a[N],b[N],fir[N],sec[N],v[N];
int get(int x,int z){if(!fir[x])fir[x]=z;else sec[x]=z;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]),get(a[i],i);
for(i=1;i<=n;i++)scanf("%d",&b[i]),get(b[i],i);
for(i=1;i<=n;i++)if(!v[i]){
v[i]=1;if(a[i]==b[i])continue;
for(p=0,q=1,x=a[j=i];;v[j=k]=1){
k=fir[x];if(k==j)k=sec[x];
if(!k||k==i)break;
if(x==b[k])q++,x=a[k];else p++,x=b[k];
}
if(!k)for(x=b[j=i];;v[j=k]=1){
k=fir[x];if(k==j)k=sec[x];
if(!k||k==i)break;
if(x==b[k])p++,x=a[k];else q++,x=b[k];
}
ans+=min(p,q);
}
printf("%d",ans);
}
这届也感觉切不动了TAT，换一届简单点的切吧
评论 (0)
