数论/Trie/并查集
猜数
这题我是这样分析的……
$a*b=g*l=n=k^2 \ and \ (g|a,g|b) \Rightarrow (g*a')*(g*b' )=g*l=k^2 \\ \Rightarrow a' * b' =\frac{l}{g}=(\frac{k}{g})^2 \Rightarrow min(a'+b')=2* \sqrt{\frac{l}{g}}, max(a'+b')=1+\frac{l}{g}$
然而算ans的时候还需要再乘g……我给忘了aaarticlea/jpeg;base64,/9j/4AAQSkZJRgABAQEASABIAAD/2wBDABsSFBcUERsXFhceHBsgKEIrKCUlKFE6PTBCYFVlZF9VXVtqeJmBanGQc1tdhbWGkJ6jq62rZ4C8ybqmx5moq6T/2wBDARweHigjKE4rK06kbl1upKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKSkpKT/wAARCAA0ADgDASIAAhEBAxEB/8QAGgAAAgMBAQAAAAAAAAAAAAAAAAUCAwQGAf/EAC4QAAIBAwMDAwMCBwAAAAAAAAECAwAEEQUSIRMiMUFRYRUycQYUI1JygZHB0f/EABQBAQAAAAAAAAAAAAAAAAAAAAD/xAAUEQEAAAAAAAAAAAAAAAAAAAAA/9oADAMBAAIRAxEAPwBtqeomzMcUUfVnlOESsX1TULNt2oWgEJ8vH6VKbB/VMIfx0jtz7006XVheOdchsgg88UEoJo7iJZYmDI3gira50aQNPj3NqE6JnACcZrPHNdxnNjdSyc/ZNj/tB1VFJLTWZQdl7AUI8lR4/Iq+61u0gO1d8reoQZoGdFYtP1S21AERMQ48o3migwpE1/r7zEkRWhCj5b1p3Sr9NqfpvUb75HZiffmmjEKMk4AoEeqNNLfCNo3MQ+1VbaSR61VDA8qtEf4nH2TJscfg00vujNGrMAoB4kJxtquGWS2nihmdZkk4jk9fxQUx2M5AjlYsMZjlI70PsferNPk6DvbSwKlwBuyvhx8U0rJeWonkjZSySKeHUeB60GC6jj+t2JjUJOdxk2+3zRVeipu1a8aaQyyxnarn2ooLtKf9leT6dKQO4yQ/INM5xvjdAeceKXPpkt2iTXMpW5XlCPCV7DdXtp23sJlUcdWIZP8AcUFNtcXU0ARlt50Pa8QPcKjNbiERvDJLiBg4icenxUhaadfOZlUh2Od8bYOatt9Pusskl27W/oHGW/zQNIpFljV0OVYZFErbY3YDJAJpdCzWFx0iM28jdhGe0+1MiNy4x5oFOlYNwjgdzw5fAxzmivNGikt725glGNo7P6c0UDiiiigx3GnWsxaQxhJMZ3pwaXTzXFrlUuZGA/nwf9UUUGB9SurhJI5JO3g8ADFdVGcxqfiiigyXHbqVqw4LBlPyMUUUUH//2Q==" alt="" />
//UOJ Easy Round1 A
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
const int N=1e5+;
/*******************template********************/ LL n,g,l;
int main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
#endif
int T; scanf("%d",&T);
while(T--){
scanf("%lld%lld",&g,&l);
printf("%lld %lld\n",*(LL)sqrt(l/g)*g,l+g);
}
return ;
}
跳蚤OS
Trie树+go指针
所以我们其实只要实现一个沿着Trie树和go指针走的Find函数就可以（找到该字符串在Trie中的实际位置）
这里需要特判一下根目录，因为只有它一个是以'\'结尾的。
这个……yy出来以后实现还是比较容易的。
坑爹的是strlen函数是O(n)的，所以最好拿一个变量来保存这个值。（优化了一下，用时居然rank1了，真是令人感动）
//UOJ Easy Round1 B
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=1e6+;
/*******************template********************/ int c[N][],go[N],fa[N],n,m,tot=;
char s1[N],s2[N],t[N];
inline int id(char ch){
if (ch=='/') return ;
else return ch-'a';
}
int Find(char *s){
int x=,y;
int l=strlen(s);
rep(i,l){
y=id(s[i]);
if (!c[x][y]){
c[x][y]=++tot;
fa[tot]=x;
t[tot]=s[i];
}
x=c[x][y];
if ((s[i+]=='/'||i+==l) && go[x]) x=go[x];
}
return x;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
F(i,,n){
scanf("%s%s",s1,s2);
int t1=Find(s1),t2=Find(s2);
if (t2==) t2=;
go[t1]=t2;
}
F(i,,m){
scanf("%s",s1);
int num=;
for(int t1=Find(s1);t1!=;t1=fa[t1])
s2[num++]=t[t1];
if (num==) s2[num++]='/';
D(i,num-,) printf("%c",s2[i]); puts("");
}
return ;
}
DZY Loves Graph
离线模拟+并查集 按秩合并 按size合并
Orz pyz5715
虽然题解看懂了，但是并不会写……
这里是用一个数组记录下来我们每插入一条边，当前的边权和，连通块个数（如果为1则成了一棵树，可以出解了），以及修改了谁的father。
merge操作就是修改这三个东西……
考虑Remove，也就是删掉一条边：
如果最后一次加边并没有修改father，那么直接删就好了……cur--
否则：我们要将这条边断掉，此时由于我们保存了该时刻的边权和以及连通块个数，所以这些都不用考虑修改……唯一需要重新维护的是每个并查集的rank，这里我一开始yy的修改方式是：将从x到其所在并查集的root的rank都减去rank[x]。然而这样TLE了……FST了最后一个点（非常鬼畜，加一条边，减一条边，加两条边，减两条边……）一开始我以为是需要卡常数，照着神犇的代码一点一点改……然而其实是这里出了问题：每次要将这一条链上的每个点 i 的rank[fa[i]]-=rank[i]。（目前百思不得其解，留一个坑吧）
这里我们离线做，做完一个操作后先读一下，看下下一个操作是不是Remove，如果是就直接执行。（这里我的感觉是为了方便知道要撤销的操作是什么）
UPD：2015年6月24日 09:06:56（Orz zyf）
其实是由于循环条件写的是i!=fa[i]，然后我每次修改的是rank[i]-=rank[x]，所以会导致根那个点（i==fa[i]）没有修改……改成每次修改rank[fa[i]]-=rank[x]就可以了
//UOJ Easy Round1 C
//orz pyz5715
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;ch<'' || ch>'';ch=getchar()) if (ch=='-') r=-;
for(;ch>='' && ch<='';ch=getchar()) v=(v<<)+(v<<)-''+ch;
return r*v;
}
const int N=;
/*******************template********************/ int n,m,cur,p[N],fa[N],rank[N],size[N],x,y;
LL w[N];
char cmd; inline int getfa(int x){return fa[x]==x?x:getfa(fa[x]);} inline void Merge(int x,int y,int val){
x=getfa(x), y=getfa(y);
w[++cur]=w[cur-]; p[cur]=;
size[cur]=size[cur-];
if (x==y) return;
if (rank[x]<rank[y]) swap(x,y);
fa[p[cur]=y]=x; rank[x]+=rank[y];
w[cur]+=val; --size[cur];
} inline void Remove(){
int x=p[cur--];
if (x){
for(int i=x;i!=fa[i];i=fa[i])
rank[fa[i]]-=rank[x];
fa[x]=x;
}
}
inline char getc(){
char ch;
while(ch=getchar(),ch< || ch>);
return ch;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
#endif
n=getint(); m=getint();
F(i,,n) fa[i]=i,rank[i]=;
size[]=n;
cmd=getc();
F(i,,m){
if (cmd=='A'){
x=getint(),y=getint();
Merge(x,y,i);
printf("%lld\n",size[cur]==?w[cur]:);
if (i!=m && (cmd=getc())=='R') Remove();
}else if (cmd=='D'){
x=getint();
printf("%lld\n",size[cur-x]==?w[cur-x]:);
if (i!=m && (cmd=getc())!='R') while(x--) Remove();
}else{
printf("%lld\n",size[cur]==?w[cur]:);
if (i!=m) cmd=getc();
}
}
return ;
}