white_bear

HUST

3373

#include<bits/stdc++.h>
using namespace std;
//统一维护当前点到根节点的距离作差就是相对距离
//d表示到根的距离
//max(0,|dx-dy|-1)//当x=y的时候就是0
//1.让排头当根节点
//2.移动的时候每个dx要加上加到的 的列的size
//d[pa]=size[pb]
//size[pb]+=size[pa]
const int N=30010;
int m;
int p[N],siz[N],d[N];
int find(int x)
{
if(p[x]!=x)
{
int root=find(p[x]);
d[x]+=d[p[x]];
p[x]=root;
}
return p[x];
}
int main()
{
cin>>m;
for(int i=1;i<N;i++)
{
p[i]=i;
siz[i]=1;
d[i]=0;
}
while(m--)
{
char  op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0]=='M')
{
int pa=find(a),pb=find(b);
d[pa]+=siz[pb];
siz[pb]+=siz[pa];
p[pa]=pb;
}
else
{
int pa=find(a),pb=find(b);
if(pa!=pb)puts("-1");
else printf("%d\n",max(0,abs(d[a]-d[b])-1));
}
}
return 0;
}


#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 20010;

int n, m;
int p[N], d[N];
unordered_map<int, int> S;

int get(int x)
{
if (S.count(x) == 0) S[x] = ++ n;
return S[x];
}

int find(int x)
{
if (p[x] != x)
{
int root = find(p[x]);
d[x] += d[p[x]];
p[x] = root;
}
return p[x];
}

int main()
{
cin >> n >> m;
n = 0;

for (int i = 0; i < N; i ++ ) p[i] = i;

int res = m;
for (int i = 1; i <= m; i ++ )
{
int a, b;
string type;
cin >> a >> b >> type;
a = get(a - 1), b = get(b);

int t = 0;
if (type == "odd") t = 1;

int pa = find(a), pb = find(b);
if (pa == pb)
{
if (((d[a] + d[b]) % 2 + 2) % 2 != t)
{
res = i - 1;
break;
}
}
else
{
p[pa] = pb;
d[pa] = (d[a] +d[b] + t)%2;
}
}

cout << res << endl;

return 0;
}


#include<bits/stdc++.h>
using namespace std;
//由于限制条件只有2e6,但是数据范围很大是0~1e9
//故我们把0~1e9映射到0~2e6
//先考虑相等约束，再考虑不相等约束
//xi!=xj矛盾说明xi与xj在同一个集合中
const int N=2e6+10;
int n,m;
int p[N];
unordered_map<int,int> S;
struct query{
int x,y,e;
}query[N];
int get(int x)
{
if(S.count(x)==0)S[x]=++n;
return S[x];
}
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int main()
{
int T;
cin>>T;
while(T--)
{
n=0;
S.clear();
scanf("%d",&m);
for(int i=0;i<m;i++)
{
int x,y,e;
scanf("%d%d%d",&x,&y,&e);
query[i]={get(x),get(y),e};
}
for(int i=1;i<=n;i++)
p[i]=i;
//合并相等约束条件
for(int i=0;i<m;i++)
if(query[i].e==1)
{
int pa=find(query[i].x),pb=find(query[i].y);
p[pa]=pb;
}
//检查所有不等条件
bool has_conflict=false;
for(int i=0;i<m;i++)
if(query[i].e==0)
{
int pa=find(query[i].x),pb=find(query[i].y);
if(pa==pb){
has_conflict=true;
break;
}
}
if(has_conflict)puts("NO");
else puts("YES");
}

return 0;
}


#include<bits/stdc++.h>
using namespace std;
//把一个连通块看成一个物品
//连通块的价值就是这里面合起来买的价值
//把钱看成容量,价值看成最大价值
int n,m,vol;
const int N=10010;
int v[N],w[N];
int p[N];
int f[N];
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int main(){
cin>>n>>m>>vol;
for(int i=1;i<=n;i++)
p[i]=i;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
while(m--)
{
int a,b;
cin>>a>>b;
int pa=find(a),pb=find(b);
if(pa!=pb)
{   v[pb]+=v[pa];
w[pb]+=w[pa];
p[pa]=pb;
}
}
//0-1背包问题
for(int i=1;i<=n;i++)
if(p[i]==i)
{
for(int j=vol;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[vol]<<endl;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
//处理环
//当两个点属于同一个集合里，连边后就成环
//把二维坐标变成一维坐标
//(x,y)->x*n+y,前提是x,y都是从0开始的
const int N=40010;
int n,m;
int p[N];

int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int get(int x,int y)
{
return x*n+y;
}
int main(){
cin>>n>>m;
for(int i=0;i<n*n;i++)//变成一维后要从0开始
p[i]=i;
int res=0;
for(int i=1;i<=m;i++)
{
int x,y;
char d;
cin>>x>>y>>d;
x--,y--;
int a=get(x,y);
int b;
if(d=='D')b=get(x+1,y);
else b=get(x,y+1);
int pa=find(a),pb=find(b);
if(pa==pb)
{
res=i;
break;
}
else p[pa]=p[pb];
}
if(!res)puts("draw");
else cout<<res<<endl;

return 0;
}


#include<bits/stdc++.h>
using namespace std;
//从剩余的数中找出第k小的数->sum(x)=k
//删除某一个数
const int N=100010;
int n;
int h[N];
int ans[N];
int tr[N];
int lowbit(int x)
{
return x&-x;
}
{
for(int i=x;i<=n;i+=lowbit(i))
tr[i]+=c;
}
int sum(int x)
{
int res=0;
for(int i=x;i>=1;i-=lowbit(i))
res+=tr[i];
return res;
}
int main(){
cin>>n;
for(int i=2;i<=n;i++)
cin>>h[i];
for(int i=1;i<=n;i++)tr[i]=lowbit(i);
for(int i=n;i>=1;i--)
{
int k=h[i]+1;//第k小
int l=1,r=n;
while(l<r)
{
int mid=l+r>>1;
//找第一个=k的
if(sum(mid)>=k)r=mid;//会把后面>=k的都剪掉,后面的=k的就用不到了
else l=mid+1;
}
ans[i]=r;
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<endl;

return 0;
}


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int n,m;
int a[N];
ll tr1[N];//表示bi的前缀和,b是个差分数组
ll tr2[N];//表示bi*i的前缀和
int lowbit(int x)
{
return x&-x;
}
{
for(int i=x;i<=n;i+=lowbit(i))
tr[i]+=c;
}
ll sum(ll tr[],int x)
{
ll res=0;
for(int i=x;i>=1;i-=lowbit(i))
res+=tr[i];
return res;
}
ll prefix_sum(int x)
{
return sum(tr1,x)*(x+1)-sum(tr2,x);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
int b=a[i]-a[i-1];
}
while(m--)
{
char op[2];
int l,r ,d;
scanf("%s%d%d",op,&l,&r);
if(*op=='Q')
{
printf("%lld\n",prefix_sum(r)-prefix_sum(l-1));
}
else
{
scanf("%d",&d);
}
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
//f(i,j)从(i,j)开始滑动的路径
//属性:Max
//一定是没有环的，因为每一次都在递减
const int N=310;
int n,m;
int h[N][N];
int f[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int dp(int x,int y){
int &v=f[x][y];
if(v!=-1)return v;
v=1;
for(int i=0;i<4;i++)
{
int a=x+dx[i];
int b=y+dy[i];
if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b]<h[x][y])
v=max(v,dp(a,b)+1);
}
return v;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>h[i][j];

memset(f,-1,sizeof f);
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
res=max(res,dp(i,j));
cout<<res<<endl;

return 0;
}


#include<bits/stdc++.h>
using namespace std;
//f(u,0)->表示的是以u为根的所有个子树中选择，并且不选u的方案
//f(u,1)->表示的是以u为根的所有子树中选，并且选择u这个点的方案
//f(u,0)=Σmax(f(s,0),f(s,1))
//f(u,1)+Σf(si,0)
//总儿子的个数等于边的个数 O(n)
const int N=6010;
int n;
int happy[N];
int h[N],ne[N],e[N],idx;
int f[N][2];
bool has_father[N];
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){
f[u][1]=happy[u];
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
dfs(j);
f[u][0]+=max(f[j][0],f[j][1]);
f[u][1]+=f[j][0];
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>happy[i];
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
has_father[a]=true;
}
int root=1;
while(has_father[root])root++;
dfs(root);
cout<<max(f[root][0],f[root][1])<<endl;
return 0;
}


#include<bits/stdc++.h>
using namespace std;
//0~n-1每个都走一次
//f(i,j)表示的是从0到j,走过的所有点是i的所有路径
//i=(1110011)从右开始表示第0 1 4 5 6都走过了
//属性->数量
//状态计算:
//0->k->j
//f(i,j)=f(i-{j},k)+a(k,j)
const int N=20,M=1<<N;
int n;
int w[N][N];
int f[M][N];
int main(){
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>w[i][j];
//在零号点，所以第0位上是1
memset(f,0x3f,sizeof f);
f[1][0]=0;
for(int i=0;i<1<<n;i++)
for(int j=0;j<n;j++)
if(i>>j&1)//
for(int k=0;k<n;k++)
if((i-(1<<j))>>k&1)
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);

cout<<f[(1<<n)-1][n-1]<<endl;
return 0;
}