日常比赛
前三题easy模拟略过
第四题就dp吧也还好
T5 写个最小生成树和并查集，贪心思想（不会证那多达114514行的证明过程
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define Sig signed
#define ll long long
#define int ll
#define Il inline
#define pii pair<int,int>
#define Vt vector
#define Stk stack
#define Que queue
#define PQ priority_queue
#define mpr make_pair
#define ft first
#define sd second
#define pb push_back
#define Mset(x,y) memset(x,y,sizeof x)
#define Mcpy(x,y) memcpy(x,y,sizeof x)
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define fdown(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define fupt(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define fdownt(i,a,b) for(int (i)=(a);(i)>(b);(i)--)
using namespace std;
const int N=3e5+10;
Il int read()
{
int p=0,q=1;
char ch=getchar();
while(!isdigit(ch)) q=(ch=='-')?-1:1,ch=getchar();
while(isdigit(ch)) p=(p<<3)+(p<<1)+(ch^48),ch=getchar();
return p*q;
}
int n,tot,ans,m,f[N];
int find(int u)
{
return (f[u]==u)?u:(f[u]=find(f[u]));
}
void merge(int u,int v)
{
f[find(u)]=find(v);
return ;
}
struct node{
int x,y,z,id;
}a[N];
struct edge{
int val,x,y;
bool operator < (const edge &kfc) const
{
return val < kfc.val;
}
}e[N];
bool cmpx(node ax,node ay){return ax.x<ay.x;}
bool cmpy(node ax,node ay){return ax.y<ay.y;}
bool cmpz(node ax,node ay){return ax.z<ay.z;}
void kruskal ()
{
sort(e+1,e+1+m);
fup(i,1,m)
{
if(tot==1) break;
int u=e[i].x,v=e[i].y,w=e[i].val;
if(find(u)==find(v)) continue;
merge(find(u),find(v));
tot--;
ans+=w;
}
return;
}
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
n=read();
fup(i,1,n) a[i]={read(), read(), read(), i};
sort(a+1,a+1+n,cmpx);
fupt(i,1,n) e[++m]={abs(a[i].x-a[i+1].x),a[i].id,a[i+1].id};
sort(a+1,a+1+n,cmpy);
fupt(i,1,n) e[++m]={abs(a[i].y-a[i+1].y),a[i].id,a[i+1].id};
sort(a+1,a+1+n,cmpz);
fupt(i,1,n) e[++m]={abs(a[i].z-a[i+1].z),a[i].id,a[i+1].id};
fup(i,1,n) f[i]=i;
tot=n;
kruskal();
printf("%lld",ans);
return 0;
}
T6 DP?张超超短AC代码！！！！！
//代码片段
n=read();
fup(i,1,n) a[i]=read();
for(int l=1;l<=n;l++)
{
mx=0;
fdown(r,n,l)
{
if(a[l]==a[r]) dp[r]=max(dp[r],mx+(l!=r)+1);
else if(a[l]>a[r]) mx=max(mx,dp[r]);
ans=max(ans,dp[r]);
}
}
printf("%d\n",ans);
T7 赛时网络流写T了 60分
改了114.514%个下午终于A了
（约等于甚么都没改
//G-code ?
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define Sig signed
#define int long long
#define Il inline
#define pii pair<int,int>
#define re register
#define Mul multiset
#define Vt vector
#define Stk stack
#define Que queue
#define Itt iterator
#define PQ priority_queue
#define umap unordered_map
#define uset unordered_set
#define ull unsigned ll
#define uint unsigned int
#define mpr make_pair
#define ft first
#define sd second
#define pb push_back
#define Mset(x,y) memset(x,y,sizeof x)
#define Mcpy(x,y) memcpy(x,y,sizeof y)
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define fdown(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define fupt(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define fdownt(i,a,b) for(int (i)=(a);(i)>(b);(i)--)
using namespace std;
const int N=2e4+5,M=45,inf=0x3f3f3f3f3f3f3f3f;
Il int read()
{
int p=0,q=1;
char ch=getchar();
while(!isdigit(ch)) q=(ch=='-')?-1:1,ch=getchar();
while(isdigit(ch)) p=(p<<3)+(p<<1)+(ch^48),ch=getchar();
return p*q;
}
int T,n,m,s,t;
int head[N],nxt[N],to[N],edge[N];
int dis[N];
int cur[N];
int tot=-1,Mx,cntx,cnty,sumx,sumy,a[M][M];
Que<int> q;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
Il void insert(int u,int v,int w){nxt[++tot]=head[u],to[tot]=v,edge[tot]=w,head[u]=tot; return;}
Il int bfs()
{
Mset(dis,-1);
dis[s]=1,q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=nxt[i])
{
int v=to[i];
if(edge[i]&&dis[v]==-1) dis[v]=dis[u]+1,q.push(v);
}
}
if(dis[t]!=-1) return 1;
else return 0;
}
Il int dfs(int u,int flow)
{
if(u==t) return flow;
int now=flow;
for(int &i=cur[u];i!=-1;i=nxt[i])
{
cur[u]=i;
int v=to[i];
if(dis[v]==dis[u]+1&&edge[i]>0)
{
int minn=dfs(v,min(now,edge[i]));
edge[i]-=minn,edge[i^1]+=minn,now-=minn;
}
if(now<=0) break;
}
return flow-now;
}
Il int dinic()
{
int res=0;
while (bfs())
{
Mcpy(cur,head);
res+=dfs(s,inf);
}
return res;
}
Il int cal(int x,int y) {return (x-1)*m+y;}
Il int check(int val)
{
if(Mx>val) return 0;
s=n*m+1,t=n*m+2,tot=-1;
Mset(head,-1);
Mset(nxt,0);
Mset(to,0);
Mset(edge,0);
fup(i,1,n)
{
fup(j,1,m)
{
int u=cal(i,j);
if((i+j)%2)
{
insert(s,u,val-a[i][j]),insert(u,s,0);
fup(k,0,3)
{
int tx=i+dx[k],ty=j+dy[k];
int v=cal(tx,ty);
if (tx>=1&&tx<=n&&ty>=1&&ty<=m) insert(u,v,inf),insert(v,u,0);
}
}
else insert(u,t,val-a[i][j]),insert(t,u,0);
}
}
if(dinic()==(val*cntx-sumx)) return 1;
else return 0;
}
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
T=read();
while(T--)
{
n=read(),m=read();
cntx=cnty=sumx=sumy=Mx=0;
fup(i,1,n)
{
fup(j,1,m)
{
Mx=max(a[i][j]=read(),Mx);
if((i+j)%2) cntx++,sumx+=a[i][j];
else cnty++,sumy+=a[i][j];
}
}
if(cntx!=cnty)
{
int now=(sumy-sumx)/(cnty-cntx);
if(check(now)) printf("%lld\n",now*cntx-sumx);
else puts("-1");
}
else
{
if(sumx!=sumy) puts("-1");
int ans=-1,l=Mx,r=inf,mid;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld\n",(ans==-1)?(-1):(ans*cntx-sumx));
}
}
return 0;
}
思路很简单，但写炸了114514次！！！
T8 线段树+倍增
题解思路混乱，看不懂，还是好好听张超讲吧
今日温度 零下114514摄氏度
所在地点 南极外国语
科研成果 A5补2
hh 天冷了，该睡了