D1T1(Vigenere)
题意：给你一个原串与一个密码串，问你按照题意规则加密后的密文。
解题思路：暴力模拟。
#include <stdio.h> int k[105],c[1005],u1[105],u2[1005]; void read(int*a,int*b){ char c; while(c=getchar(),c>='a'&&c<='z'||c>='A'&&c<='Z') if(c>='a'&&c<='z')a[++a[0]]=c-'a'; else a[++a[0]]=c-'A',b[a[0]]=1;; } int main(){ read(k,u1);read(c,u2);int j=0; for(int i=1;i<=c[0];i++) { j++;if(j==k[0]+1)j=1; c[i]=(c[i]-k[j]+26)%26; } for(int i=1;i<=c[0];i++) if(u2[i]==1)putchar(c[i]+'A'); else putchar(c[i]+'a'); }
D1T2(game)
题意：n个物品，每个物品有2个val，然后按照题目当中的价值计算方式计算，求使得价值最高的物品最小的价值。
解题思路：考虑最后一个大臣，显然他很可能是金币最多的人。我们要让他的金币尽量的少。之前的大臣左手的数肯定会乘起来，所以我们要使S/A/B尽量的大。（设S 是左手所有数的乘积），即让A*B尽量的大。选完最后一个后，我们把他踢掉，然后再找一个最后的大臣。如此往复，相当于就是对A*B排序。然后就直接按照上述思路进行处理，剩下的就是高精度，压4位就可以直接计算了。
#include <stdio.h> #include <string.h> #include <algorithm> #define MN 1005 struct sv{ int a,b; inline bool operator <(const sv &y)const{ return a*b<y.a*y.b; } }t[MN]; struct hpc{ int num[MN],len; inline bool operator <(const hpc &b)const{ if (len^b.len) return len<b.len; for (int i=len-1; i>=0; --i) if (num[i]^b.num[i]) return num[i]<b.num[i]; return 0; } inline hpc operator *(int b)const{ hpc ans;int &leng=ans.len; memset(ans.num,0,sizeof(ans.num)); for (int i=0; i<len; ++i){ ans.num[i]+=num[i]*b;ans.num[i+1]+=ans.num[i]/10000; ans.num[i]%=10000; }ans.len=len; for (; ans.num[leng]; ++leng){ ans.num[leng+1]=ans.num[leng]/10000;ans.num[leng]%=10000; }return ans; } inline hpc operator /(int b)const{ hpc ans;int &leng=ans.len; memset(ans.num,0,sizeof(ans.num)); for (int i=len-1; i; --i){ ans.num[i-1]+=(ans.num[i]+num[i])%b*10000; ans.num[i]=(ans.num[i]+num[i])/b; } ans.num[0]=(ans.num[0]+num[0])/b; for (ans.len=len; !ans.num[leng-1]; --leng); return ans; } inline void print(){ printf("%d",num[len-1]); for (int i=len-2; i>=0; --i) printf("%.4d",num[i]); } }sum,res;int n; int main(){ scanf("%d",&n); for (int i=0;i<=n;i++){ scanf("%d%d",&t[i].a,&t[i].b); }sum.num[0]=t[0].a;sum.len=1; std::sort(t+1,t+n+1); for (int i=1;i<=n;i++){ hpc tmp=sum/t[i].b; if (res<tmp) res=tmp; sum=sum*t[i].a; }res.print(); }
D1T3(drive)
题意：有n个点，每个点有高度，两个点的距离定义为高度差的绝对值（高度越小的默认越距离相对较小）。有2个人，1个人走最近的路，另一个人走第二近的路，现在这2人轮流开车，问：(I)给定时间t，问选哪个起点两人走的路程比值最小。(II)给定起点a与时间t，问走完后2人各自走了多少。
解题思路：首先考虑如何处理距离的问题，我们需要做到的是给定一个高度，在其左右2边进行查找，显然c++STL中的set是可以较为方便的实现的。
接下来考虑如何解决问题：首先我们将轮流走一次压缩为1步，然后倍增求出走x步的距离，然后对于每次询问就只需要倍增查找即可。(I)就是暴力扫一遍找答案，(II)就是裸的询问。时间效率( O((n+m) log n) )
#include <stdio.h> #include <algorithm> #include <set> #define MN 100005 #define lg 16 #define ll long long #define inf 1e16 #define abs(a) (((a))<0?(-1*(a)):(a)) struct point{ int no,h; bool operator <(const point &b)const{ return h<b.h; } }a[MN]; struct cmpp{ int no,dis; bool operator <(const cmpp &b)const{ return dis<b.dis||(dis==b.dis&&a[no].h<a[b.no].h); } }tmp[5]; using std::set; set<point> pt; int n,m,x0,na[MN],nb[MN],ans; ll fa[MN][lg+1],da[MN][lg+1],db[MN][lg+1],ansa=inf,ansb=0ll; inline int in(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } inline void prework(int k){ set<point>::iterator it=pt.find(a[k]); register int j=0; if (it!=pt.begin()){ --it;tmp[++j].no=it->no,tmp[j].dis=abs(it->h-a[k].h); if (it!=pt.begin()){ --it;tmp[++j].no=it->no,tmp[j].dis=abs(it->h-a[k].h);++it; }++it; } if ((++it)!=pt.end()){ tmp[++j].no=it->no,tmp[j].dis=abs(it->h-a[k].h); if ((++it)!=pt.end()){ tmp[++j].no=it->no,tmp[j].dis=abs(it->h-a[k].h); } } std::sort(tmp+1,tmp+1+j); nb[k]=tmp[1].no; if (j==1) return; na[k]=tmp[2].no; } inline void getans(int u,int t,ll &ta,ll &tb){ for (register int i=lg; i>=0; --i) if (fa[u][i]&&da[u][i]+db[u][i]<=t){ ta+=da[u][i],tb+=db[u][i]; t-=da[u][i]+db[u][i];u=fa[u][i]; } if (da[u][0]<=t) ta+=da[u][0]; } void init(){ n=in();for (int i=1; i<=n; ++i) a[i].h=in(),a[i].no=i; for (register int i=n; i; --i) {pt.insert(a[i]);if (i!=n) prework(i);} } void st(){ for (register int i=1; i<=n; ++i){ register int p1=na[i],p2=nb[na[i]]; da[i][0]=p1?abs(a[p1].h-a[i].h):0; db[i][0]=p2?abs(a[p2].h-a[p1].h):0; fa[i][0]=p2; } for (int j=1; j<=lg; ++j) for (register int i=1; i<=n; ++i){ fa[i][j]=fa[fa[i][j-1]][j-1]; da[i][j]=da[i][j-1]+da[fa[i][j-1]][j-1]; db[i][j]=db[i][j-1]+db[fa[i][j-1]][j-1]; } } void solve(){ st();x0=in(); for (register int i=1; i<=n; ++i){ register ll ta=0ll,tb=0ll; getans(i,x0,ta,tb); if (tb&&(!ans||ansa*tb>ansb*ta)) ans=i,ansa=ta,ansb=tb; } printf("%d ",ans);m=in(); for (register int i=1; i<=m; ++i){ register int x=in(),t=in(); register ll ta=0ll,tb=0ll; getans(x,t,ta,tb); printf("%lld %lld ",ta,tb); } } int main(){init();solve();return 0;}
D2T1(mod)
题意：看题目。
解题思路：裸的exgcd，注意一下答案要取最小正整数。
#include <stdio.h> inline void exgcd(int a,int b,int &x,int &y){ if (!b){x=1,y=0; return;} exgcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; } int main(){ int a,b,x,y; scanf("%d%d",&a,&b); exgcd(a,b,x,y); x=(x+b)%b;printf("%d",x); }
D2T2(classroom)
题意：有n天，每天有r[i]间教室，有m个任务，这个任务占用一个时间段中的若干间教室，问按顺序满足最多可以满足多少间。
解题思路：二分答案，然后差分统计第i天借了教室的数量，check即可。时间效率：( O(nlog n) )
#include <stdio.h> #include <string.h> #define MN 1000005 #define mid (l+r>>1) int cf[MN],n,m,s[MN],t[MN],d[MN],r[MN]; inline int in(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') f=ch=='-'?-1:1,ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } inline bool check(int ans){ memset(cf,0,sizeof(cf)); for (register int i=1; i<=ans; ++i) cf[s[i]-1]+=d[i],cf[t[i]]-=d[i]; register int tmp=cf[0]; for (register int i=1; i<=n; tmp+=cf[i++]) if (tmp>r[i]) return 0; return 1; } void init(){ n=in(),m=in(); for (int i=1; i<=n; ++i) r[i]=in(); for (register int i=1; i<=m; ++i) d[i]=in(),s[i]=in(),t[i]=in(); } void solve(){ int l=0,r=m; for (;l<r; check(mid)?l=mid+1:r=mid); if (r==m) puts("0"); else printf("-1 %d",r); } int main(){init();solve();return 0;}
D2T3(blockade)
题意：在一棵树上，有m个可以移动的东西，树的边有权值，若根到某个节点上有东西，那么就无法遍历到某个节点，问无法遍历到所有叶节点的最小时间。
解题思路：首先倍增预处理，然后考虑二分答案，紧接着对于二分出来的答案，让所有的东西在时限内尽可能的往上爬，能爬到根节点的记录下来，接下来先dfs找出根节点的子节点子树中是否存在没有所有叶节点都无法遍历到，然后贪心即可。时间效率 ( O(nlog n + (mlog {mn} + n）log Ans) ).
#include <stdio.h> #include <algorithm> #include <string.h> #define MN 50005 #define lg 15 #define ll long long #define v edge[i].to #define mid (l+r>>1) char B[1<<26],*S=B,C;int X; inline int in(){ while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } struct edg{ int to,nxt,val; bool friend operator <(const edg &a,const edg &b){ return a.val<b.val; } }edge[MN<<1],ste[MN]; struct tas{ int tim,lstpos; bool friend operator <(const tas &a,const tas &b){ return a.tim<b.tim; } }task[MN]; int head[MN],n,m,l,r,cnt,fa[MN][lg+1],cntt,pos[MN],count; bool vis[MN],isleaves[MN],used[MN];ll dis[MN]; inline void ins(int x,int y,int val){edge[++cnt].to=y,edge[cnt].nxt=head[x],head[x]=cnt,edge[cnt].val=val;} inline void pre(int u,int f,ll d){ fa[u][0]=f,dis[u]=d;register bool b=1; for (register int i=head[u]; i; i=edge[i].nxt) if (v!=f) b=0,pre(v,u,d+edge[i].val); if (b) isleaves[u]=1; } void init(){ fread(B,1,1<<26,stdin);n=in(); for (int i=1; i<n; ++i){ register int x=in(),y=in(),val=in(); ins(x,y,val);ins(y,x,val); if (x==1||y==1) ste[++cntt].to=x==1?y:x,ste[cntt].val=val; } std::sort(ste+1,ste+cntt+1); m=in();if (m<cntt){puts("-1");return;} for (register int i=1; i<=m; ++i) pos[i]=in(); pre(1,0,0); for (int j=1; j<=lg; ++j) for (register int i=1; i<=n; ++i) fa[i][j]=fa[fa[i][j-1]][j-1]; } inline bool dfs(int u){ register bool p=1;if (vis[u]) return 1; if (isleaves[u]) return 0; for (register int i=head[u]; i; i=edge[i].nxt) if (v!=fa[u][0]) p&=dfs(v); return vis[u]=p; } inline bool uptree(int no,int tim){ register int u=pos[no]; for (register int i=lg; i>=0; --i) if (fa[u][i]>1&&dis[pos[no]]-dis[fa[u][i]]<=tim) u=fa[u][i]; if (fa[u][0]==1&&dis[pos[no]]<tim) { task[++count].lstpos=u,task[count].tim=tim-dis[pos[no]]; }else vis[u]=1; } inline bool check(int ans){ count=0;memset(vis,0,sizeof(vis)); for (register int i=1; i<=m; ++i) uptree(i,ans); dfs(1);std::sort(task+1,task+count+1); register int p=1; for (register int i=1; i<=count; ++i) if (!vis[task[i].lstpos]) vis[task[i].lstpos]=1; else{ while(vis[ste[p].to]&&p<=cntt) ++p;if (p>cntt) return 1; if (task[i].tim>=ste[p].val) vis[ste[p].to]=1; } while(vis[ste[p].to]) ++p;return p>cntt; } void solve(){ int l=0,r=1e9; for (;l<r; check(mid)?r=mid:l=mid+1); printf("%d",r); } int main(){init();solve();return 0;}