1001
并查集。考虑按点权大到小把点插入图中，每次插入点到图中，我们不妨设集合(S)(其中(s_i)为第(i)个集合的权值)为与当前点相连的连通块组成的集合，(w)为当前节点的权值。易得插入一个点得到的新连通块的公式为：
[sum^S (s_i-w)+w
]
那么维护集合我们很自然的想到用并查集维护。最后扫一遍每个点，保证每个连通块都加入答案。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
#define PII pair <int,int>
#define fr first
#define sc second
#define mp make_pair
const int N=1e5+7;
int n,m;
ll Ans=0;
vector <int> G[N];
PII a[N];
ll vis[N],ans[N];
int fa[N],rk[N],vs[N];
int find(int x){ return fa[x]==x? x:(fa[x]=find(fa[x]));}
void merge(int x,int y){
x=find(x);y=find(y);
x==y? 0:rk[x]>=rk[y]? fa[y]=x,rk[x]+=rk[y]:fa[x]=y,rk[y]+=rk[x];
}
int main(){
int T=input();
while(T--){
n=input(),m=input();
int sta=1;Ans=0;
for(int i=1;i<=n;i++){
int val=input();
a[i]=mp(val,i);
fa[i]=i,rk[i]=1,G[i].clear();
vis[i]=0,ans[i]=0;vs[i]=0;
}
for(int i=1;i<=m;i++){
int u=input(),v=input();
G[u].push_back(v),G[v].push_back(u);
}
sort(a+1,a+1+n);
for(int i=n;i>=1;i--){
int u=a[i].sc,val=a[i].fr;
int cnt=0;
for(auto v:G[u]){
if(vis[v]){
if(find(u)!=find(v)) ans[u]+=(ans[find(v)]-val);
merge(u,v);
}
}
vis[u]=1;
ans[find(u)]=ans[u]+val;
}
ll res=0;
for(int i=1;i<=n;++i){
if(vs[find(i)]==0) res+=ans[find(i)],vs[find(i)]=1;
}
printf("%lld
",res);
}
}
1012
比赛的时候dp没推出来，就是菜☹。我们观察到B串非常短(m)最大只有20，我们考虑把复杂度尽量与询问的区间长度无关，与B串的长度有关。我们这个时候想到了一个非常好用的结构序列自动机，序列自动机能够让我们在原串上快速移动，这样我们的所有操作就与区间长度无关，而与(m)有关了。
现在问题转换为如何通过序列自动机，求区间的LCS，为啥要求LCS，因为我编辑距离只有增加和删除，那么最优一定是尽可能的保留更多的字符不被删除，那么我们就很自然的想到要求LCS，最后答案一定是在原串中要删掉多少个字符((r-l+1-LCS))加上要加入多少个字符使得答案匹配的数量(|B|-LCS)，即((r-l+1-LCS)+|B|-LCS)。我们不妨记区间([l,r])的LCS为(LCS(l,r))，那么我们求(LCS(l,r))，需要考虑(dp[i][j])表示开始(B)的前(i)个位置匹配长度为(j)的LCS最远能到哪里。那么转移方程易得:
[dp[i][j]=min(dp[i][j],nxt[dp[i-1][j-1]][s[i]-'a'])
]
最后扫一遍(dp[m][i])求答案即可。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=1e5+7;
int nxt[N][27];
char a[N],b[N];
int lena,lenb;
void init(){
memset(nxt,0,sizeof nxt);
int len=strlen(a+1);
for(int i=0;i<26;i++) nxt[len][i]=1e9;
for(int i=len;i>=1;i--){
for(int j=0;j<=25;j++) nxt[i-1][j]=nxt[i][j];
nxt[i-1][a[i]-'a']=i;
}
}
int dp[27][27];
ll getans(int l,int r){
memset(dp,0x3f,sizeof dp);
dp[0][0]=l-1;
for(int i=1;i<=lenb;i++){
dp[i][0]=l-1;
for(int j=1;j<=i;j++){
dp[i][j]=dp[i-1][j];
if(dp[i-1][j-1]<=r){
dp[i][j]=min(dp[i][j],nxt[dp[i-1][j-1]][b[i]-'a']);
}
}
}
int res=1e9;
for(int i=0;i<=lenb;i++){
if(dp[lenb][i]<=r) res=min(res,(r-l+1-i)+(lenb-i));
}
return res;
}
int main(){
int T=input();
while(T--){
scanf("%s%s",a+1,b+1);
init();
lena=strlen(a+1),lenb=strlen(b+1);
int Q=input();
for(int i=1;i<=Q;i++){
int l=input(),r=input();
printf("%lld
",getans(l,r));
}
}
}
1006
感觉是温暖的签到?要你计算(A*B=C)，然后某一位(1)被篡改位(0),那么显然枚举哪一位被篡改就行了，然后发现这个(A，B，C)数特别大，然后要考虑同余，为了避免题目出现误差，所以不能使fib的前(2*10^6)项同余。随便搞一手自然溢出，就过了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned int
uint input(){
uint x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=2e6+7;
uint f[N];
void init(){
f[0]=1,f[1]=1;
for(int i=2;i<N;i++) f[i]=f[i-1]+f[i-2];
}
int c[N];
int main(){
init();
int T=input();
while(T--){
uint A=0,B=0,C=0;
int n,m,p,t;
n=input();for(int i=1;i<=n;i++) A+=(f[i]*input());
m=input();for(int i=1;i<=m;i++) B+=(f[i]*input());
p=input();for(int i=1;i<=p;i++) c[i]=input(),C+=(f[i]*c[i]);
uint tmp=A*B;
for(int i=1;i<=p;i++){
if(c[i]) continue;
if(C+f[i]==tmp){
printf("%d
",i);
break;
}
}
}
}
1010
温暖的签到题。搜索就完事了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=57;
struct node{
ll a,b,c,d;
};
vector<node> a[N],b[N];
int n,k;
ll Ans=0;
void dfs(int dep,ll A,ll B,ll C,ll D){
if(dep>k){Ans=max((100+A)*(100+B)*(100+C)*(100+D),Ans);return;}
for(int i=0;i<b[dep].size();i++){
dfs(dep+1,A+b[dep][i].a,B+b[dep][i].b,C+b[dep][i].c,D+b[dep][i].d);
}
}
int main(){
int T=input();
while(T--){
n=input(),k=input();
for(int i=1;i<=k;i++) a[i].clear();Ans=0;
for(int i=1;i<=n;i++){
int t=input(),_a=input(),_b=input(),_c=input(),_d=input();
a[t].push_back((node){_a,_b,_c,_d});
}
int cnt=0;
for(int i=1;i<=k;i++) if(a[i].size()) b[++cnt]=a[i];
k=cnt;
dfs(1,0,0,0,0);
printf("%lld
",Ans);
}
}
1005
简单费用流。容易建模n个人跟m个机器连一条边，边流量为(1)，费用为(a_i*j^2+b_i*j+c_i)。但是发现(m)太大了，直接建图根本存不下，我们需要缩减图的规模，我们贪心的想一条增广路的权值一定在二次函数最低点的附近，我们可以通过三分法简单的得到包括中点长为n的区间，为了保险我把边的区间扩大了5倍。然后由于我们取点是取一个区间的若干段，所以我们需要对取到的点进行离散化。然后就跑MCMF，保留每次求到增广路的花费即可。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=1007*1007;
const ll INF=0x3f3f3f3f3f3f3f;
#define PII pair <ll,ll>
#define fr first
#define sc second
#define mp make_pair
#define dbg printf("PASS IN LINE %d
",__LINE__);
vector <ll> Ans;
struct MinCostFlow{
struct edge{
ll v,f,c,r;
edge(ll _v, ll _f, ll _c, ll _r) :v(_v), f(_f), c(_c), r(_r) {}
};
ll V=0,h[N],dis[N],pv[N],pe[N];
vector <edge> G[N];
inline void init(ll n){
for(ll i=0;i<=V;i++) G[i].clear();
V=n;
}
inline void Ins(ll u,ll v,ll f,ll c){
G[u].push_back(edge(v,f,c,G[v].size() ));
G[v].push_back(edge(u,0,-c,G[u].size()-1 ));
}
PII MCMF(ll s,ll t,ll Flow){
ll cost=0,flow=0,newflow;fill(h,h+1+V,0);
while(Flow){
priority_queue <PII,vector<PII>,greater<PII> > Q;
fill(dis,dis+V+1,INF);
dis[s]=0,Q.push(mp(0,s));
while(!Q.empty()){
PII now=Q.top();Q.pop();
ll u=now.sc;
if(dis[u]<now.fr) continue;
for(ll i=0;i<G[u].size();i++){
edge &e=G[u][i];
if(e.f>0&&dis[e.v]>dis[u]+e.c+h[u]-h[e.v]){
dis[e.v]=dis[u]+e.c+h[u]-h[e.v];
pv[e.v]=u,pe[e.v]=i;
Q.push(PII(dis[e.v],e.v));
}
}
}
if(dis[t]==INF) break;
for(ll i=0;i<=V;i++) h[i]+=dis[i];
newflow=Flow;
for(ll x=t;x!=s;x=pv[x]) newflow=min(newflow,G[pv[x]][pe[x]].f);
Flow-=newflow,flow+=newflow,cost+=newflow*h[t];
Ans.push_back(cost);
for(ll x=t;x!=s;x=pv[x]){
edge &e=G[pv[x]][pe[x]];
e.f-=newflow;
G[x][e.r].f+=newflow;
}
}
return mp(flow,cost);
}
}A;
struct node{
ll a,b,c;
}wk[N];
ll n,m;
ll cal(ll a,ll b,ll c,ll j){
return a*j*j+b*j+c;
}
PII getmin(ll a,ll b,ll c){
ll l=1,r=1e8;
while(r-l+1>=min(n,m)){
ll mid1=(2*l+r)/3,mid2=(l+2*r)/3;
if(cal(a,b,c,mid1)<cal(a,b,c,mid2)) r=mid2;
else l=mid1;
}
return mp(l,r);
}
vector<ll> v;
map <PII,int> p;
int getid(ll x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void work(){
Ans.clear();v.clear();
for(int i=1;i<=n;i++){
PII tmp=getmin(wk[i].a,wk[i].b,wk[i].c);
for(int j=max(tmp.fr-2*n,1ll);j<=min(tmp.sc+2*n,m);j++){
v.push_back(j);
}
}
sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());
A.init((n+v.size()+1));
int cnt=0;
for(int i=1;i<=n;i++){
PII tmp=getmin(wk[i].a,wk[i].b,wk[i].c);
for(int j=max(tmp.fr-2*n,1ll);j<=min(tmp.sc+2*n,m);j++){
A.Ins(i,n+getid(j),1,cal(wk[i].a,wk[i].b,wk[i].c,j));
p[mp(i,n+getid(j))]=1;
}
}
int s=0,t=n+v.size()+1;
for(int i=1;i<=n;i++){
A.Ins(s,i,1,0);
}
for(int i=1;i<=v.size();i++){
A.Ins(i+n,t,1,0);
}
PII tmp=A.MCMF(s,t,INF);
sort(Ans.begin(),Ans.end());
for(int i=0;i<Ans.size();i++){
printf("%lld%c",Ans[i],i==Ans.size()-1? '
':' ');
}
}
int main(){
int T=input();
while(T--){
n=input(),m=input();
for(int i=1;i<=n;i++){
wk[i].a=input(),wk[i].b=input(),wk[i].c=input();
}
work();
}
}