先总结一波
第一次打cf，感觉还不错，题目做得挺顺手。虽然开始30min才想起来有这么个比赛来着。。
纪念一下第一次的rank，话说题真是水
这是大概还剩下5min的时候截的，实际可能会掉一点吧
第二天更新：
原来d题真的会被卡，果然还是要tarjan找一个环来删边
hacking真是有趣，
A Garden
直接扫一遍出解
#include <stdio.h>
#include <algorithm>
using namespace std;
int a[201];
int main(void) {
int n,m; scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
int ans=0x3f3f3f3f;
for (int i=1;i<=n;i++) {
if (m%a[i]==0) ans=min(ans,m/a[i]);
}
printf("%d\n", ans);
}B Browser
交了几次才对，而且每次都错同一个点，晕
注意分类，当pos
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main(void) {
int n,pos,l,r;
scanf("%d%d%d%d",&n,&pos,&l,&r);
int ans=0;
if (l<=pos&&pos<=r) {
if (l==1&&r==n) {
ans=0;
} else if (l==1&&r!=n) {
ans=r-pos+1;
} else if (l!=1&&r==n) {
ans=pos-l+1;
} else if (l!=1&&r!=n) {
ans=min(pos-l+1+r-l+1,r-pos+1+r-l+1);
}
} else if (pos<l) {
if (r==n) {
ans=l-pos+1;
} else {
ans=l-pos+1+r-l+1;
}
} else if (pos>=r) {
if (l==1) {
ans=pos-r+1;
} else {
ans=pos-r+1+r-l+1;
}
}
printf("%d\n", ans);
return 0;
}C Permute Digits
类似数位dp，贪心地想当高位肯定越大越好，同时记录flag表示是否贴着放，dfs即可
#include <stdio.h>
#include <string.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
char a[20],b[20];
int cnt[10],c[20];
bool find=false;
void dfs(int dep,bool flag) {
if (find) return ;
if (dep==strlen(b)+1) {
find=true;
rep(i,strlen(b)-strlen(a)+1,dep-1) {
printf("%d", c[i]);
}
return ;
}
drp(i,9,0) if ((!flag||i<=b[dep-1]-'0')&&cnt[i]) {
c[dep]=i;
cnt[i]--;
dfs(dep+1,flag&(i==(b[dep-1]-'0')));
cnt[i]++;
c[dep]=0;
}
}
int main(void) {
scanf("%s", a); scanf("%s", b);
rep(i,0,strlen(a)-1) cnt[a[i]-'0']++;
dfs(strlen(b)-strlen(a)+1,strlen(b)==strlen(a));
return 0;
}D Almost Acyclic Graph
枚举边删掉跑拓扑排序，第一眼以为要强连通分量缩小删边的范围呢。。
更新：果然被hack了。正解应该是tarjan找一个环然后枚举这个环上的边来删。因为是简单环因此只有n-1条边，这样就是n^2的了
#include <stdio.h>
#include <string.h>
#include <queue>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
const int N=505;
const int E=100005;
struct edge{int x,y,vis,next;}e[E];
std:: queue<int> que;
int ls[N],d[N],rec[N],edCnt=0;
void addEdge(int x,int y) {
e[++edCnt]=(edge){x,y,0,ls[x]};
ls[x]=edCnt; rec[y]++;
}
int top_sort(int n) {
while (!que.empty()) que.pop();
rep(i,1,n) d[i]=rec[i];
rep(i,1,n) if (!d[i]) que.push(i);
int count=0;
while (!que.empty()) {
int now=que.front(); que.pop();
count++;
for (int i=ls[now];i;i=e[i].next) {
if (e[i].vis) continue;
if (!(--d[e[i].y])) {
que.push(e[i].y);
}
}
}
return count==n;
}
int main(void) {
int n,m; scanf("%d%d",&n,&m);
rep(i,1,m) {
int x,y; scanf("%d%d",&x,&y);
addEdge(x,y);
}
rep(i,1,edCnt) {
e[i].vis=1;
rec[e[i].y]--;
if (top_sort(n)) {
puts("YES");
return 0;
}
rec[e[i].y]++;
e[i].vis=0;
}
puts("NO");
return 0;
}E Physical Education Lessons
直接开一棵线段树，空间不够考虑动态开点。注意数组要开得合适不然大了小了都会被卡(滑稽
#include <stdio.h>
#include <string.h>
const int M=300005;
struct treeNode{int l,r,sum,lazy;}t[M*50];
int root=1,cnt=1;
void push_down(int now,int tl,int tr) {
if (t[now].lazy==-1) return ;
if (!t[now].l) t[t[now].l=++cnt]=(treeNode){0,0,0,-1};
if (!t[now].r) t[t[now].r=++cnt]=(treeNode){0,0,0,-1};
int mid=(tl+tr)>>1;
t[t[now].l].lazy=t[t[now].r].lazy=t[now].lazy;
t[t[now].l].sum=(mid-tl+1)*t[now].lazy;
t[t[now].r].sum=(tr-mid)*t[now].lazy;
t[now].lazy=-1;
}
void modify(int &now,int tl,int tr,int l,int r,int v) {
if (!now) t[now=++cnt]=(treeNode){0,0,0,-1};
if (tl==l&&tr==r) {
t[now].sum=(r-l+1)*v;
t[now].lazy=v;
return ;
}
push_down(now,tl,tr);
int mid=(tl+tr)>>1;
if (r<=mid) modify(t[now].l,tl,mid,l,r,v);
else if (l>mid) modify(t[now].r,mid+1,tr,l,r,v);
else {
modify(t[now].l,tl,mid,l,mid,v);
modify(t[now].r,mid+1,tr,mid+1,r,v);
}
t[now].sum=t[t[now].l].sum+t[t[now].r].sum;
}
int query(int now,int tl,int tr,int l,int r) {
if (!now) return 0;
if (tl==l&&tr==r) return t[now].sum;
push_down(now,tl,tr);
int mid=(tl+tr)>>1;
if (r<=mid) return query(t[now].l,tl,mid,l,r);
else if (l>mid) return query(t[now].r,mid+1,tr,l,r);
else return query(t[now].l,tl,mid,l,mid)+query(t[now].r,mid+1,tr,mid+1,r);
}
int main(void) {
int n,m; scanf("%d%d",&n,&m);
t[root].sum=n; t[root].lazy=1;
while (m--) {
int l,r,k; scanf("%d%d%d",&l,&r,&k);
if (k==1) {
modify(root,1,n,l,r,k-1);
} else if (k==2) {
modify(root,1,n,l,r,k-1);
}
printf("%d\n", query(root,1,n,1,n));
}
return 0;
}F
当时没写出来，但是现在还是改出来了
之前做过类似的题目，我还是太弱了
可以分别求最大值的贡献和最小值的贡献。以最大值为例，按点权排序后并查集维护连通块，只需要计算此时经过这个点路径条数*点权即可
cf不能用%lld真是神奇
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
#define fill(x,t) memset(x,t,sizeof(x))
typedef long long ll;
const int N=2000005;
const int E=4000005;
struct edge{int x,y,next;}e[E];
int fa[N],rank[N],size[N],v[N];
int ls[N],edCnt=0;
bool vis[N];
void addEdge(int x,int y) {
e[++edCnt]=(edge){x,y,ls[x]}; ls[x]=edCnt;
e[++edCnt]=(edge){y,x,ls[y]}; ls[y]=edCnt;
}
int get_father(int now) {
return (!fa[now])?(now):(fa[now]=get_father(fa[now]));
}
bool cmp(int x,int y) {return v[x]<v[y];}
int main(void) {
// freopen("data.in","r",stdin);
// freopen("myp.out","w",stdout);
int n; scanf("%d",&n);
rep(i,1,n) {
scanf("%I64d",&v[i]);
rank[i]=i;
}
rep(i,2,n) {
int x,y; scanf("%d%d",&x,&y);
addEdge(x,y);
}
std:: sort(rank+1,rank+n+1,cmp);
ll ans=0;
fill(fa,0); fill(vis,0);
rep(i,1,n) size[i]=1;
drp(ti,n,1) {
int now=rank[ti]; vis[now]=1;
for (int i=ls[now];i;i=e[i].next) {
if (!vis[e[i].y]) continue;
int fx=get_father(now),fy=get_father(e[i].y);
ans-=(ll)size[fx]*size[fy]*v[now];
size[fx]+=size[fy];
fa[fy]=fx;
}
}
// printf("%I64d\n", ans);
fill(fa,0); fill(vis,0);
rep(i,1,n) size[i]=1;
rep(ti,1,n) {
int now=rank[ti]; vis[now]=1;
for (int i=ls[now];i;i=e[i].next) {
if (!vis[e[i].y]) continue;
int fx=get_father(now),fy=get_father(e[i].y);
ans+=(ll)size[fx]*size[fy]*v[now];
size[fx]+=size[fy];
fa[fy]=fx;
}
}
printf("%I64d\n", ans);
return 0;
}G
不会，日后更新吧