NOIP 2012 提高组 合集
D1 T1 Vigenère 密码
模拟题，观察到两个数对应位置-1相加的和%26就是对应的字母，按照这个性质模拟即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char frm1[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char frm2[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int calc(char c)
{
if(c>='a'&&c<='z') return c-'a';
return c-'A';
}
char s1[2010],s2[110],s3[2010];
int main()
{
scanf("%s%s",s2+1,s1+1);
int k1=strlen(s1+1),k2=strlen(s2+1),k3=0;
int cnt=k1/k2+((k1%k2==0)?0:1);
// printf("Shit %d
",cnt);
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=k2;j++) s3[++k3]=s2[j];
}
// printf("%s
%s
",s1+1,s3+1);
// for(int i=0;i<=25;i++) cout << calc(frm2[i]) << " " ;
for(int i=1;i<=k1;i++)
{
int x1=calc(s1[i]),x2=calc(s3[i]);
char c;
if(s1[i]>='a'&&s1[i]<='z') c=frm2[(x1+26-x2)%26];
else c=frm1[(x1+26-x2)%26];
// puts("Fuck");
putchar(c);
// cout << s1[i] << s3[i] << (x1+x2)%26 << " " << x1+x2 << " " << c << endl ;
}
return 0;
}
D1 T2 国王游戏
通过简单的小推导我们可以发现自己的$a_i*b_i$越大的越靠后越优，然后开心之余发现这个题的考点是高精度... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
int n,l=1,a[N],b[N],c[N],g[N*10];
using namespace std;
void dispose1(int x)
{
for(int i=1;i<=l;i++) g[i]*=b[x];
for(int i=1;i<=l;i++)
{
g[i+1]+=(g[i]/10);
g[i]%=10;
}
l++;
while(g[l]>9)
{
g[l+1]+=(g[l]/10);
g[l]%=10;
l++;
}
if(g[l]==0) l--;
}
void dispose2()
{
for(int i=l;i>=1;i--)
{
g[i-1]+=((g[i]%c[n])*10);
g[i]/=c[n];
}
while(g[l]==0) l--;
if(l==0) puts("1");
}
void qsort(int l,int r)
{
int i=l,j=r,mid=a[(l+r)/2];
while(i<=j)
{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
int t=a[i]; a[i]=a[j]; a[j]=t;
t=b[i]; b[i]=b[j]; b[j]=t;
t=c[i]; c[i]=a[j]; c[j]=t;
i++; j--;
}
}
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);
}
int main()
{
scanf("%d",&n);
scanf("%d %d",&b[0],&c[0]);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&b[i],&c[i]);
a[i]=b[i]*c[i];
}
qsort(1,n);
g[1]=b[0];
for(int i=1;i<n;i++) dispose1(i);
dispose2();
for(int i=l;i>=1;i--) printf("%d",g[i]);
return 0;
}
D1 T3 开车旅行
一眼dp题。
状态：dp[i][j][k]，表示从i开始走了2^j步，第k个人走了多少。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define N 100005
#define INF 10000000000000ll
using namespace std;
int n,starx,height[N],f[N][20][5],dp1[N][20][3],dp2[N][20][3];
struct Node
{
int idx,data;
friend bool operator<(const Node &a,const Node &b) {return a.data<b.data;}
};
multiset<Node>s;
void calc(int S,int &a,int &b,int x)
{
int now=S;
for(int k=18;~k;k--)
{
if(f[now][k][0]&&a+b+dp1[now][k][0]+dp2[now][k][0]<=x)
{
a+=dp1[now][k][0];
b+=dp2[now][k][0];
now=f[now][k][0];
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&height[i]);
Node a;
height[0]=2e9;height[n+1]=-2e9;
a.idx=0;a.data=2e9;s.insert(a);s.insert(a);
a.idx=n+1;a.data=-2e9;s.insert(a);s.insert(a);
for(int i=n;i;i--)
{
int goa,gob; Node aa;
aa.idx=i,aa.data=height[i];
s.insert(aa);
set<Node>::iterator it=s.lower_bound(aa);
int pre,nxt;
int preh,nxth;
it++; nxt=(*it).idx; nxth=(*it).data;
it--;it--; pre=(*it).idx; preh=(*it).data;
it++;
if(abs(nxth-height[i])>=abs(preh-height[i]))
{
gob=pre;
it--;it--;
if(abs(nxth-height[i])>=abs((*it).data-height[i])) goa=(*it).idx;
else goa=nxt;
}
else
{
gob=nxt;
it++;it++;
if(abs(preh-height[i])>abs((*it).data-height[i])) goa=(*it).idx;
else goa=pre;
}
f[i][0][0]=goa;
f[i][0][1]=gob;
dp1[i][0][0]=abs(height[i]-height[goa]);
dp1[i][1][0]=dp1[i][0][0];
dp2[i][0][1]=abs(height[i]-height[gob]);
dp2[i][1][1]=dp2[i][0][1];
}
for(int i=1;i<=n;i++)
{
f[i][1][0]=f[f[i][0][0]][0][1];
dp1[i][1][0]=dp1[i][0][0];
dp2[i][1][0]=abs(height[f[i][1][0]]-height[f[i][0][0]]);
f[i][1][1]=f[f[i][0][1]][0][0];
dp2[i][1][1]=dp2[i][0][1];
dp1[i][1][1]=abs(height[f[i][1][1]]-height[f[i][0][1]]);
}
for(int k=2;k<=18;k++)
{
for(int i=1;i<=n;i++)
{
f[i][k][1]=f[f[i][k-1][1]][k-1][1];
dp2[i][k][1]=dp2[f[i][k-1][1]][k-1][1]+dp2[i][k-1][1];
dp1[i][k][1]=dp1[i][k-1][1]+dp1[f[i][k-1][1]][k-1][1];
f[i][k][0]=f[f[i][k-1][0]][k-1][0];
dp1[i][k][0]=dp1[i][k-1][0]+dp1[f[i][k-1][0]][k-1][0];
dp2[i][k][0]=dp2[i][k-1][0]+dp2[f[i][k-1][0]][k-1][0];
}
}
scanf("%d",&starx);
double ans=INF*10.0;
int idx;
for(int i=1;i<=n;i++)
{
int la=0,lb=0;
calc(i,la,lb,starx);
if(!lb)
{
if(ans>INF) ans=INF,idx=i;
else if(ans==INF&&height[idx]<height[i]) idx=i;
}
else
{
double now=(double)la/(double)lb;
if(now<ans) ans=now,idx=i;
else if(now==ans&&height[idx]<height[i]) idx=i;
}
}
printf("%d
",idx);
int cases;
scanf("%d",&cases);
while(cases--)
{
int a,b;
int la=0,lb=0;
scanf("%d%d",&a,&b);
calc(a,la,lb,b);
printf("%d %d
",la,lb);
}
return 0;
}
D2 T1 同余方程
exgcd裸题。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b) x=1,y=0;
else
{
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
}
int main()
{
ll a,b; cin >> a >> b ;
ll x,y; exgcd(a,b,x,y);
ll d=__gcd(a,b);
x=(x%b/d+b/d)%b/d;
cout << x << endl ;
}
D2 T2 借教室
线段树大法好，$10^6$开始没想到nlogn能过，数组没开够。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson pos<<1
#define rson pos<<1|1
#define N 1000010
using namespace std; int tag[N<<2],minn[N<<2],a[N];
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
inline void pushup(int pos) {minn[pos]=min(minn[lson],minn[rson]);}
inline void pushdown(int pos)
{
if(!tag[pos]) return;
minn[lson]+=tag[pos]; tag[lson]+=tag[pos];
minn[rson]+=tag[pos]; tag[rson]+=tag[pos];
tag[pos]=0;
}
void build(int l,int r,int pos)
{
if(l==r) {minn[pos]=a[l]; return;}
int mid=(l+r)>>1;
build(l,mid,lson); build(mid+1,r,rson);
pushup(pos);
}
void update(int x,int y,int val,int l,int r,int pos)
{
if(x<=l&&r<=y) {minn[pos]-=val; tag[pos]-=val; return;}
pushdown(pos); int mid=(l+r)>>1;
if(x<=mid) update(x,y,val,l,mid,lson);
if(mid<y) update(x,y,val,mid+1,r,rson);
pushup(pos);
}
int query(int x,int y,int l,int r,int pos)
{
if(x<=l&&r<=y) return minn[pos];
pushdown(pos); int mid=(l+r)>>1,ans=0x7f7f7f7f;
if(x<=mid) ans=min(ans,query(x,y,l,mid,lson));
if(mid<y) ans=min(ans,query(x,y,mid+1,r,rson));
return ans;
}
int main()
{
int n=rd(),m=rd(); for(int i=1;i<=n;i++) a[i]=rd(); build(1,n,1);
for(int s,t,v,i=1;i<=m;i++)
{
v=rd(),s=rd(),t=rd();
if(query(s,t,1,n,1)<v) {printf("-1
%d
",i); return 0;}
update(s,t,v,1,n,1);
}
puts("0");
return 0;
}
D2 T3 疫情控制
先二分每个军队往上走多少。显然在没有到达根节点之前越往上越优。如果军队可以到达根节点判断这个军队可不可以上去然后原路返回，如果不可以显然是停留在原地更优，反之都移动到根节点上单独考虑。
#include <iostream>
#include <cstdio>
#include <queue>
#include <ctime>
#include <cstring>
#include <algorithm>
#define N 50005
using namespace std;
typedef long long ll;
int n,m;
struct E{
int to,nxt;
ll d;
}b[N*2];
int fst[N],tot;
void add(int f,int t,ll d)
{
b[++tot]=(E){t,fst[f],d};fst[f]=tot;
b[++tot]=(E){f,fst[t],d};fst[t]=tot;
}
ll dis[N];
int fa[N][20];
int top[N];
int pe[N];
bool cmp(int a,int b)
{
if(dis[a]!=dis[b])
return dis[a]>dis[b];
return a<b;
}
bool isf[N];
int sz[N];
void dfs(int x,int p)
{
top[x]=p;
for(int i=1;i<=16;i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=fst[x];i;i=b[i].nxt)
{
int v=b[i].to;
if(!fa[v][0])
{
fa[v][0]=x;
dis[v]=dis[x]+b[i].d;
dfs(v,p);sz[x]++;
}
}
if(!sz[x])isf[x]=true;
}
bool vis[N];
int nd[N],C;
queue<int> Q;
void bfs(ll mid)
{
Q.push(1);C=0;vis[1]=1;
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=fst[u];i;i=b[i].nxt)
{
int v=b[i].to;
if(!vis[v])
{
if(isf[v])
nd[++C]=top[v];
else Q.push(v);
vis[v]=1;
}
}
}
sort(nd+1,nd+C+1,cmp);
C=unique(nd+1,nd+C+1)-nd-1;
}
ll stack[N];int Top;
bool check(ll mid)
{
memset(vis,0,sizeof(vis));Top=0;
for(int i=1;i<=m;i++)
{
int u=pe[i];int v=top[u];
ll cst=dis[u]-dis[v];
if(vis[v]||dis[u]+dis[v]<=mid)
{
ll p=mid-dis[u];
stack[++Top]=p;
}
else if(cst<=mid)vis[v]=1;
else
{
int p=u;ll res=mid;
for(int j=16;j>=0;j--)
{
int w=fa[p][j];
ll wv=dis[p]-dis[w];
if(wv<=res){p=w;res-=wv;}
}
while(sz[fa[p][0]]==1&&!vis[p])
vis[p]=1,p=fa[p][0];
vis[p]=1;
}
}
bfs(mid);
int H=1;
for(int i=C;i>=1;i--)
{
ll p=dis[nd[i]];
while(stack[H]<p&&H<=Top)H++;
if(H>Top) return false;H++;
}
return true;
}
int main()
{
scanf("%d",&n);
int u,v;ll d;
int cnt=0;
for(int i=1;i<n;i++)
{
scanf("%d%d%lld",&u,&v,&d);
add(u,v,d);
if(u==1||v==1) cnt++;
}
for(int i=0;i<=18;i++)fa[1][i]=1;
for(int i=fst[1];i;i=b[i].nxt)
{
int v=b[i].to;
dis[v]=b[i].d;
fa[v][0]=1;
dfs(v,v);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d",&pe[i]);
sort(pe+1,pe+m+1,cmp);
if(m<cnt)
{
puts("-1");
return 0;
}
ll l=-1,r=1e9,mid;
while(r-l>1)
{
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
cout << r << endl ;
}