NOIp2012题解
时间：2019-10-21 10:11:13
收藏：0
阅读：51
题目链接：https://loj.ac/problems/search?keyword=NOIP2012
D1T1
暴力
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,m,ans[1010],op[1010],a[1010],b[1010];
char s[1010],t[1010];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
scanf("%s",s+1);
scanf("%s",t+1);
n=strlen(s+1);m=strlen(t+1);
rep(i,1,n)
{
if ((s[i]>='a') && (s[i]<='z'))
{
a[i]=s[i]-'a';
}
else
{
a[i]=s[i]-'A';
}
}
rep(i,1,m)
{
if ((t[i]>='a') && (t[i]<='z'))
{
b[i]=t[i]-'a';
}
else
{
b[i]=t[i]-'A';
op[i]=1;
}
}
rep(i,1,m)
{
int id=(i-1)%n+1;
ans[i]=(b[i]-a[id]+26)%26;
}
rep(i,1,m)
if (op[i]) putchar(ans[i]+'A');
else putchar(ans[i]+'a');
return 0;
}D1T2
记前面的人的左手边前缀和为\(P\)，当前两个人的左手上的数字为\(l_1,l_2\)，右手上的数字为\(r_1,r_2\)，并且1在2前面时最大花费更少，那么有\(max(\frac{P}{r_1},\frac{Pl_1}{r_2})\leq max(\frac{P}{r_2},\frac{Pl_2}{r_1})\)
首先我们注意到\(\frac{P}{r_1}<\frac{Pl_2}{r_1},\frac{P}{r_2}<\frac{Pl_1}{r_2}\)，因此我们只需要比较后面两个数的大小，可以得到\(\frac{l_1}{r_2}<\frac{l_2}{r_1}\)即\(l_1r_1<l_2r_2\)。于是我们只要将所有人按照\(l_ir_i\)的大小排序即可
但是注意到最后的答案可能很大，于是就需要手写一个高精度
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,m;
pii p[100100];
bool cmp(pii x,pii y)
{
return 1ll*x.fir*x.sec<1ll*y.fir*y.sec;
}
struct bigint{
int len,a[5100];
void init()
{
memset(a,0,sizeof(a));len=1;
}
void print()
{
per(i,len,1) printf("%d",a[i]);
puts("");
}
};
bigint operator *(bigint x,int y)
{
bigint z;z.init();z.len=x.len;
rep(i,1,x.len) z.a[i]=x.a[i]*y;
rep(i,1,x.len)
{
z.a[i+1]+=z.a[i]/10;
z.a[i]=z.a[i]%10;
}
while (z.a[z.len+1])
{
z.len++;
z.a[z.len+1]+=z.a[z.len]/10;
z.a[z.len]=z.a[z.len]%10;
}
return z;
}
bigint operator /(bigint x,int y)
{
bigint z;z.init();z.len=x.len;
ll now=0;
per(i,x.len,1)
{
now=now*10+x.a[i];
z.a[i]=now/y;
now%=y;
}
while ((!z.a[z.len]) && (z.len)) z.len--;
return z;
}
bool operator <(bigint x,bigint y)
{
if (x.len<y.len) return 1;
if (x.len>y.len) return 0;
per(i,x.len,1)
if (x.a[i]>y.a[i]) return 0;
else if (x.a[i]<y.a[i]) return 1;
return 0;
}
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
n=read();
p[0].fir=read();p[0].sec=read();
rep(i,1,n) {p[i].fir=read();p[i].sec=read();}
sort(p+1,p+1+n,cmp);
bigint now,ans;now.init();
now.a[1]=1;now.len=1;
now=now*p[0].fir;ans=now/p[1].sec;
rep(i,1,n)
{
bigint tmp=now/p[i].sec;
ans=max(ans,tmp);
now=now*p[i].fir;
}
ans.print();
return 0;
}D1T3
预处理出在每一个位置小A/B向后走一步到达的位置，使用set解决
不难发现第一问和第二问是相同的，都是给一个起始点\(s\)和最长运动距离\(x\)，求小A和小B所走过的路径
这个可以使用倍增解决，记一轮操作表示小A和小B都走了一步。\(to[i][j]\)表示从\(i\)出发走了\(2^j\)轮之后的位置，\(disa[i][j]\)表示小A从\(i\)出发在\(2^j\)轮中所走过的距离，\(disb[i][j]\)表示小B从\(i\)出发在\(2^j\)轮中所走过的距离。之后所有的询问倍增跳跳跳就可以了。注意处理最后一轮可能只有小A向前走的情况
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,m,to[100100][21],toa[100100],tob[100100];
ll disa[200200][21],disb[100100][21],nowa=0,nowb=0;
pii p[100100];
set<pii> s;
set<pii>::iterator it1,it2;
vector<pii> tmp;
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
bool cmp(pii x,pii y)
{
return ((x.fir<y.fir) || ((x.fir==y.fir) && (p[x.sec].fir<p[y.sec].fir)));
}
void find(int id)
{
it1=s.lower_bound(p[id]);
tmp.clear();
if (it1!=s.begin())
{
--it1;
tmp.push_back(make_pair(abs(it1->fir-p[id].fir),it1->sec));
if (it1!=s.begin())
{
--it1;
tmp.push_back(make_pair(abs(it1->fir-p[id].fir),it1->sec));
}
}
it1=s.lower_bound(p[id]);it1++;
if (it1!=s.end())
{
tmp.push_back(make_pair(abs(it1->fir-p[id].fir),it1->sec));
it1++;
if (it1!=s.end())
{
tmp.push_back(make_pair(abs(it1->fir-p[id].fir),it1->sec));
}
}
sort(tmp.begin(),tmp.end(),cmp);
int len=tmp.size();
tob[id]=tmp[0].sec;
if (len>1) toa[id]=tmp[1].sec;
}
void init()
{
n=read();
rep(i,1,n)
{
p[i].fir=read();p[i].sec=i;
}
per(i,n,1)
{
s.insert(p[i]);
if (i!=n)
{
find(i);
int ta=toa[i],tb=tob[ta];
if (ta) disa[i][0]=abs(p[ta].fir-p[i].fir);
if (tb) disb[i][0]=abs(p[tb].fir-p[ta].fir);
to[i][0]=tb;
}
}
per(i,n,1)
{
rep(j,1,20)
{
to[i][j]=to[to[i][j-1]][j-1];
disa[i][j]=disa[i][j-1]+disa[to[i][j-1]][j-1];
disb[i][j]=disb[i][j-1]+disb[to[i][j-1]][j-1];
}
}
}
void work(int st,int lim)
{
int now=st;
per(i,20,0)
{
if ((to[now][i]) && (disa[now][i]+disb[now][i]<=lim))
{
lim-=(disa[now][i]+disb[now][i]);
nowa+=disa[now][i];nowb+=disb[now][i];
now=to[now][i];
}
}
if (toa[now])
{
if (lim>=disa[now][0])
{
lim-=disa[now][0];
nowa+=disa[now][0];
}
}
}
void solve1(int lim)
{
int ans=0;ll ansa=0,ansb=0;
rep(st,1,n)
{
nowa=0;nowb=0;
work(st,lim);
if ((nowb) && ((!ans) || (nowa*ansb<nowb*ansa)))
{
ansa=nowa;ansb=nowb;ans=st;
}
}
printf("%d\n",ans);
}
void solve2()
{
m=read();
while (m--)
{
nowa=0;nowb=0;
int st=read(),lim=read();
work(st,lim);
printf("%lld %lld\n",nowa,nowb);
}
}
int main()
{
init();
solve1(read());
solve2();
return 0;
}D2T1
扩欧模板题
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
if (b==0) {x=1;y=0;return;}
else
{
exgcd(b,a%b,x,y);
ll tmpx=x,tmpy=y;
x=tmpy;y=tmpx-a/b*tmpy;
}
}
int main()
{
int a=read(),b=read();
ll x=0,y=0;exgcd(a,b,x,y);
x=(x%b+b)%b;
printf("%lld",x);
return 0;
}D2T2
反正我想到了两种做法
1）二分答案+差分check
2）线段树
由于好久没写线段树了就写了棵线段树
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
int n,m,seg[4004000],tag[4004000],a[4004000];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
void build(int id,int l,int r)
{
if (l==r)
{
seg[id]=a[l];return;
}
int mid=(l+r)>>1;
build(id<<1,l,mid);build(id<<1|1,mid+1,r);
seg[id]=min(seg[id<<1],seg[id<<1|1]);
}
void pushdown(int id)
{
if (tag[id])
{
seg[id<<1]-=tag[id];seg[id<<1|1]-=tag[id];
tag[id<<1]+=tag[id];tag[id<<1|1]+=tag[id];
tag[id]=0;
}
}
void modify(int id,int l,int r,int ql,int qr,int val)
{
pushdown(id);
if ((l>=ql) && (r<=qr))
{
seg[id]-=val;tag[id]+=val;
return;
}
int mid=(l+r)>>1;
if (ql<=mid) modify(id<<1,l,mid,ql,qr,val);
if (qr>mid) modify(id<<1|1,mid+1,r,ql,qr,val);
seg[id]=min(seg[id<<1],seg[id<<1|1]);
}
int query(int id,int l,int r,int ql,int qr)
{
pushdown(id);
if ((l>=ql) && (r<=qr)) return seg[id];
int ans=maxd,mid=(l+r)>>1;
if (ql<=mid) ans=min(ans,query(id<<1,l,mid,ql,qr));
if (qr>mid) ans=min(ans,query(id<<1|1,mid+1,r,ql,qr));
return ans;
}
int main()
{
n=read();m=read();
rep(i,1,n) a[i]=read();
build(1,1,n);
rep(i,1,m)
{
int d=read(),l=read(),r=read(),now=query(1,1,n,l,r);
//cout << now << endl;
if (now<d) {printf("-1\n%d",i);return 0;}
modify(1,1,n,l,r,d);
}
puts("0");
return 0;
}D2T3
问的东西其实是“军队最长移动时间的最小值”，于是我们考虑二分答案
一个比较显然的贪心是：在可以的情况下，使得军队所在位置的\(dep\)最小是最优的，因为它一定会比它的儿子覆盖更多的叶子节点
我们将所有的军队先尽可能的往上提，如果它到达不了\(1\)节点，那就让他在那个最远的位置定下来。对于那些能够到达\(1\)节点的军队，他们可以通过根节点来控制其他的子树，不难发现如果要这么做的话让军队驻扎在\(1\)的儿子节点一定是最优的
找到所有的可以移动的军队后，将它们的剩余距离从小到大排序。同时将\(1\)的儿子节点中有叶子没有被控制的节点拎出来，也按照到\(1\)的距离从小到大排个序。之后贪心的匹配就好了。将军队往上提的过程可以使用倍增加速，最后的时间复杂度是\(2\)个\(\log\)的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
struct node{int to,nxt,cost;}sq[100100];
int all=0,head[100100];
int n,m,q,col[10010],fa[10010][16],dis[10010][16],dep[10010];
struct edgenode{int u,v,w;}edge[50050];
bool operator<(edgenode p,edgenode q) {return p.w>q.w;}
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
void add(int u,int v,int w)
{
all++;sq[all].to=v;sq[all].nxt=head[u];sq[all].cost=w;head[u]=all;
}
int find(int x) {if (col[x]==x) return col[x];col[x]=find(col[x]);return col[x];}
void dfs(int u,int fu)
{
dep[u]=dep[fu]+1;
rep(i,1,15)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
dis[u][i]=min(dis[u][i-1],dis[fa[u][i-1]][i-1]);
}
for (int i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if (v==fu) continue;
fa[v][0]=u;dis[v][0]=sq[i].cost;
dfs(v,u);
}
}
int query(int u,int v)
{
if (dep[u]<dep[v]) swap(u,v);
int tmp=dep[u]-dep[v],ans=maxd;
per(i,15,0)
if ((tmp>>i)&1) {ans=min(ans,dis[u][i]);u=fa[u][i];}
if (u==v) return ans;
per(i,15,0)
if (fa[u][i]!=fa[v][i])
{
ans=min(ans,min(dis[u][i],dis[v][i]));
u=fa[u][i];v=fa[v][i];
}
ans=min(ans,min(dis[u][0],dis[v][0]));
return ans;
}
int main()
{
n=read();m=read();
rep(i,1,m)
{
edge[i].u=read();edge[i].v=read();edge[i].w=read();
}
sort(edge+1,edge+1+m);
rep(i,1,n) col[i]=i;
rep(i,1,m)
{
int u=edge[i].u,v=edge[i].v,w=edge[i].w;
int fx=find(u),fy=find(v);
if (fx!=fy)
{
add(u,v,w);add(v,u,w);
col[fx]=fy;
}
}
memset(dis,0x3f,sizeof(dis));
rep(i,1,n)
if (!dep[i]) dfs(i,0);
q=read();
while (q--)
{
int u=read(),v=read();
if (find(u)!=find(v)) {puts("-1");continue;}
printf("%d\n",query(u,v));
}
return 0;
}原文：https://www.cnblogs.com/encodetalker/p/11711197.html
评论（0）