完爆…挫死了.在被屠中成长.
A
可知周期只能是lcm(a,b),而lcm=a*b/gcd(a,b)，所以更替不会超过a+b次，于是直接模拟优先者的更替，计算时间比较即可。
B
模拟题。虽然这题很弱，但是给了我教训。
注意对于map
C
做的时候头一热，SG都没算直接用胜负表示状态…NIM游戏转化为有向图的模型里面，如果只有一个棋子乱走确实可以这样，但是多个棋子走就必须SG函数了…犯傻了…
本题不只是多个棋子一起走，而且每个棋子还会分裂。但是我们依然可以得出这个性质：若该状态本身各棋子xor和为0，那么无论对方下一步怎么走，我还是能使得xor和为0(NIM游戏的证明方法)。
于是SG+异或前缀和。枚举决策是O(sqrt(n))的，总复杂度O(n*sqrt(n))
#include
#include
#include
#include
#include
using namespace std;
const int N=100005;
int sg[N];
int best[N];
int Sum[N];
set
int main(){
int n;
cin >> n;
Sum[0]=0;
sg[0]=1;
fill(best+1,best+n+1,-1);
for (int i=1;i<=n;i++){
Hash.clear();
for (int k=2;(k+1)*k/2<=i;k++){
int base=(i-(k+1)*k/2);
if (base%k) continue;
base/=k;
if ( (Sum[base+k]^Sum[base])==0 )
if (best[i]==-1) best[i]=k;
Hash.insert(Sum[base+k]^Sum[base]);
}
for (int j=0;;j++)
if (!Hash.count(j)) { sg[i]=j; break; }
Sum[i]=Sum[i-1]^sg[i];
}
cout << best[n] << endl;
}
D
给一棵树，每条边有权值。n<=10^5
每两个点之间都会打一次架(A打了B，B还要打一次A)，打架以后会在路径上边权最大的边上种树。如果多条最大边，每条都种树。
问最多树的是哪些路？
按边从小到大排序，然后逐次合并点块。如果没有同权的边，这个方法就很容易用并查集实现。然后现在我们考虑同权的一块处理，因为之前的小的都合过点了，现在加了一堆同权的边以后，会构成多颗新树。然后分别对这些树DFS求出子树大小然后乘一下就得解。
时间复杂度O(n lg n)
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=100005;
struct edge{int x,y,w,label; long long cnt;}g[N*2];
int n,m;
int F[N];
int Size[N];
int sz[N];
int sum_sz[N];
int fa[N];
int v[N];
vector
vector
map
map
set
void add(int x,int y,int w,int i){
g[i].x=x; g[i].y=y; g[i].w=w; g[i].label=i; g[i].cnt=0;
}
bool cmp(edge A,edge B){
return A.w
}
int gf(int x){
if (F[x]==x) return x;
return F[x]=gf(F[x]);
}
void Union(int x,int y){
int px=gf(x);
int py=gf(y);
F[px]=py;
Size+=Size[px];
}
void dfs(int x){
v[x]=1;
happ.push_back(x);
for (vector
int y=*it;
if (!v[y]){
fa[y]=x;
dfs(y);
sum_sz[x]+=sum_sz[y];
}
}
}
void gao(int st,int ed){
m=0;
app.clear();
for (int i=st;i<=ed;i++){
int x=gf(g[i].x);
int y=gf(g[i].y);
if (!app.count(x)) app[x]=++m;
if (!app.count(y)) app[y]=++m;
}
for (int i=1;i<=m;i++)
To[i].clear();
for (int i=st;i<=ed;i++){
int x=gf(g[i].x);
int y=gf(g[i].y);
To[app[x]].push_back(app[y]);
To[app[y]].push_back(app[x]);
sz[app[x]]=Size[F[x]];
sz[app[y]]=Size[F[y]];
}
for (int i=1;i<=m;i++) { v[i]=0; sum_sz[i]=sz[i]; }
Ans.clear();
for (int i=1;i<=m;i++)
if (!v[i]){
happ.clear();
fa[i]=0;
dfs(i);
int total=sum_sz[i];
for (int k=1;k
int j=happ[k];
Ans[make_pair(j,fa[j])]=(long long)sum_sz[j]*(total-sum_sz[j]);
Ans[make_pair(fa[j],j)]=(long long)sum_sz[j]*(total-sum_sz[j]);
}
}
for (int i=st;i<=ed;i++)
g[i].cnt=Ans[make_pair(app[gf(g[i].x)],app[gf(g[i].y)])];
for (int i=st;i<=ed;i++)
Union(g[i].x,g[i].y);
}
int main(){
freopen("input.txt","r",stdin);
scanf("%d",&n);
for (int i=1;i
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
add(x,y,w,i);
}
sort(g+1,g+n,cmp);
for (int i=1;i<=n;i++) { F[i]=i; Size[i]=1; }
long long ans=-1;
for (int i=1;i
int st=i;
while (i
int ed=i;
gao(st,ed);
}
Ret.clear();
for (int i=1;i
if (g[i].cnt>ans) ans=g[i].cnt;
for (int i=1;i
if (g[i].cnt==ans) Ret.insert(g[i].label);
cout << ans*2 << " " << Ret.size() << endl;
bool first=true;
for (set
if (!first) cout << " ";
cout << *it;
first=false;
}
cout << endl;
}
被屠什么的，无所谓的。