今日得分：100+10+0，(T2T3有點毒瘤)
T1
題目大意：給你一張n個點n條邊的無向圖，滿足每條邊形如(i,t[i],w[i])，兩人輪流操作，每次可以選擇一條未被選擇的邊，要求選擇后已選擇的邊不能出現環，直到不能操作為止，先手希望選擇的邊權值之和最小，后手希望選擇的邊權值之和最大，求最終選擇的邊的權值最大，n<=1e5,t1<=[i]<=n,w[i]<=1e6，
題解：容易發現，每條邊最多在一個簡單環中，且最終一定是在每個環中找出一條邊不選，其余的邊全選，于是我們可以將原圖中每個環找出來，對于不在環中的邊直接加入答案，對于長度為奇數的環，一定是不選權值排中間的那條邊；對于長度為偶數的環，一定是不選權值排中間的兩條邊之一，且兩人選擇的順序為按照這兩條邊的差值排序后盡可能大的對自己有利的邊，直接做即可，時間復雜度O(nlogn)（排序復雜度），
AC代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
inline int re_ad()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline int mi(int x,int y){return x<y?x:y;}
int n;
int t[100010],w[100010];
vector<int> g[100010];
long long ans;
int dfn[100010],low[100010],col[100010],sum,tot;
int z[100010];
bool fla[100010];
void tarjan(int x)
{
fla[x]=true;dfn[x]=low[x]=++tot;z[++z[0]]=x;
register int i,sz=g[x].size(),v;
for(i=0;i<sz;++i)
{
v=g[x][i];
if(!dfn[v]){tarjan(v);low[x]=mi(low[x],low[v]);}
else if(fla[v])low[x]=mi(low[x],dfn[v]);
}
if(dfn[x]==low[x])
{
register int y=z[z[0]];++sum;
while(y!=x){col[y]=sum;fla[y]=false;y=z[--z[0]];}col[z[z[0]--]]=sum;fla[x]=false;
}
}
vector<int> bian[100010];
int a[100010],kx[100010],tt;
void solve()
{
register int i,j,sz,to;
for(i=1;i<=sum;++i)if(!bian[i].empty())
{
sz=bian[i].size();
for(j=0;j<sz;++j)a[j+1]=bian[i][j];
sort(a+1,a+sz+1);
if(sz&1)
{
to=sz>>1;
for(j=1;j<=to;++j)ans+=a[j];for(j=to+2;j<=sz;++j)ans+=a[j];
}
else
{
to=sz>>1;
for(j=1;j<=to;++j)ans+=a[j];for(j=to+2;j<=sz;++j)ans+=a[j];
kx[++tt]=a[to+1]-a[to];
}
}
sort(kx+1,kx+tt+1);
for(i=tt-1;i>=1;i-=2)ans+=kx[i];
}
int main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
register int i;
n=re_ad();
for(i=1;i<=n;++i){t[i]=re_ad();g[i].push_back(t[i]);}
for(i=1;i<=n;++i)w[i]=re_ad();
for(i=1;i<=n;++i)if(!dfn[i])tarjan(i);
for(i=1;i<=n;++i)
{
if(col[i]==col[t[i]])bian[col[i]].push_back(w[i]);
else ans+=w[i];
}
solve();
cout<<ans<<endl;
return 0;
}T2
題目大意：給你一個n個點的樹，求在這棵樹中任意選出m個點，最多能有多少個點與這m個點的距離都<=d，1<=m<=n<=1e6,0<=d<=n，
題解：首先顯然所有哨塔應該構成一個連通塊， 然后對于一個大小為m的連通塊，考慮它的直徑中點，設直徑長度為r，那么要求dis<=r的點個數>=m，并且次長鏈長度>=r，那么距離不超過d-r的點的個數就是答案了，長鏈剖分+換根即可維護每一個點為根的某個深度以下的點的個數， 注意到父親節點的r與當前節點的r差不超過1，因此可以做到O(n)，
T3
題目大意：定義一個長度為n的序列A是合法的，當且僅當1<=a1<=a2<=…<=an<=n，且對任意k滿足1<=k<n，從A中取出任意k+1個數的和嚴格大于從A中取出任意k個數的和，給定n，求合法的A的個數對輸入的質數p取模的結果，n<=333333,9e8<=p<1e9，
題解：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278944.html
標籤：其他