虽 iakabc 但 ABC 已经泯然众锣鼓月赛矣。
A A
语法题，无介绍。
:::info[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include<bits/stdc++.h>
#define fs first
#define sc second
#define pb push_back
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int main(){
string s;
cin>>s;
for(char c:s){
if(c!='A')putchar('.');
else putchar('A');
}
}
/*
*/
|
:::
B Break a Stick
语法题，无介绍。
:::info[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include<bits/stdc++.h>
#define fs first
#define sc second
#define pb push_back
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int l[105];
int main(){
int n,sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",l+i),sum+=l[i];
int ans=1e7+5;
int t=0;
for(int i=0;i<=n;i++){
t+=l[i];
ans=min(ans,abs(sum-2*t));
}
printf("%d\n",ans);
}
/*
*/
|
:::
C On a Diet
细节题。事实上，AtCheater 禁止 AI 翻译真是一个垃圾的选择。
:::info[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include<bits/stdc++.h>
#define fs first
#define sc second
#define pb push_back
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
ll a[200005];
int main(){
ll n,m,k;
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++)scanf("%lld",a+i);
ll sum=0;
queue<pair<int,ll>>p;
for(int i=1;i<=n;i++){
while(!p.empty()&&p.front().fs<max(i-m+1,1ll)){
sum-=p.front().sc;
p.pop();
}
if(sum+a[i]<=k){
sum+=a[i];
p.push({i,a[i]});
puts("Yes");
}else puts("No");
}
}
/*
*/
|
:::
D Bomber Mad
多源 BFS 模版题。谁不想火急火燎的打完然后忘判边界爽吃两发罚时呢。
:::info[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include<bits/stdc++.h>
#define fs first
#define sc second
#define pb push_back
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace IO{
void fastIO(){ios::sync_with_stdio(0);cin.tie(0);}
void openf(string fileName){freopen((fileName+".in").c_str(),"r",stdin);freopen((fileName+".out").c_str(),"w",stdout);}
template<typename T>T read(T &x){x=0;bool flag=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')flag=0;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}if(flag)return x;return x=(~x)+1;}
template<typename T>void write(T x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');}
}
vector<int>g[500005];
bool shang[500005],zuo[500005];
vector<bool>rea[500005];
constexpr int b[4][2]={1,0,-1,0,0,1,0,-1};
int h,w,k;
int main(){
IO::fastIO();
cin>>h>>w>>k;
for(int i=1;i<=h;i++){
string s;
cin>>s;
g[i].resize(w+1);
rea[i].resize(w+1);
for(int j=0;j<w;j++){
if(s[j]=='#'){
zuo[i]=shang[j+1]=1;
g[i][j+1]=1;
}
}
}
queue<pair<pii,int> >q;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(!zuo[i]&&!shang[j]){
q.push({{i,j},0});
rea[i][j]=1;
}
}
}
while(!q.empty()){
auto t=q.front();
q.pop();
if(t.sc==k)continue;
for(int i=0;i<4;i++){
int xx=t.fs.fs+b[i][0];
int yy=t.fs.sc+b[i][1];
if(xx>=1&&xx<=h&&yy>=1&&yy<=w&&!g[xx][yy]&&!rea[xx][yy]){
rea[xx][yy]=1;
q.push({{xx,yy},t.sc+1});
}
}
}
int ans=0;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(rea[i][j])ans++;
}
}
cout<<ans;
}
/*
*/
|
:::
E Odd Cycle
二分图染色模版题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include<bits/stdc++.h>
#define fs first
#define sc second
#define pb push_back
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
vector<int>g[200005];
int dep[200005],fa[200005];
void solve(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)g[i].clear();
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
g[u].pb(v);
g[v].pb(u);
}
queue<int>q;
dep[1]=0;
q.push(1);
for(int i=1;i<=n;i++)dep[i]=-1,fa[i]=0;
int taru=-1,tarv=-1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i:g[u]){
if(dep[i]==-1){
dep[i]=dep[u]+1;
fa[i]=u;
q.push(i);
}else if(fa[u]!=i){
if(dep[u]%2==dep[i]%2){
taru=u,tarv=i;
break;
}
}
}
if(taru!=-1)break;
}
if(taru==-1){
puts("-1");
return;
}
vector<int>pathu,pathv;
if(dep[taru]<dep[tarv])swap(taru,tarv);
while(dep[taru]>dep[tarv]){
pathu.pb(taru);
taru=fa[taru];
}
while(taru!=tarv){
pathu.pb(taru);
pathv.pb(tarv);
taru=fa[taru];
tarv=fa[tarv];
}
pathu.pb(taru);
printf("%d\n",pathu.size()+pathv.size());
for(int i=0;i<pathu.size();i++)printf("%d ",pathu[i]);
for(int i=pathv.size()-1;i>=0;i--)printf("%d ",pathv[i]);
puts("");
}
int main(){
int T;
scanf("%d",&T);
while(T--)solve();
}
|
F Centroid of a Slice
呃呃呃 AT 你在 abc 里放这种美味情何以堪。
首先我们利用 bdfs 得到多边形的有符号面积为：
$$A=\frac{1}{2} \sum_{i=0}^{n-1}(x_i y_{i+1} - x_{i+1}y_i)$$再跑一次 bdfs，得到重心 $(C_x,C_y)$ 为：
$$C_x = \frac{1}{6A} \sum_{i=0}^{n-1} (x_i + x_{i+1})(x_i y_{i+1} - x_{i+1}y_i)$$$$C_y = \frac{1}{6A} \sum_{i=0}^{n-1} (y_i + y_{i+1})(x_i y_{i+1} - x_{i+1}y_i)$$于是我们可以预处理出
$(x_i y_{i+1} - x_{i+1}y_i)$、$(x_i + x_{i+1})(x_i y_{i+1} - x_{i+1}y_i)$ 和 $(y_i + y_{i+1})(x_i y_{i+1} - x_{i+1}y_i)$ 的前缀和，然后查询的时候对于多出来的 $u \rightarrow v$ 只要加边就可以了。
:::info[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include<bits/stdc++.h>
#define fs first
#define sc second
#define pb push_back
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
struct node{
__int128 cross,tx,ty;
node operator+(const node& rhs){
return {cross+rhs.cross,tx+rhs.tx,ty+rhs.ty};
}
node operator-(const node& rhs){
return {cross-rhs.cross,tx-rhs.tx,ty-rhs.ty};
}
}pre[60005];
pii p[60005];
int n,q;
node calc(pii a,pii b){
__int128 cr=1ll*a.fs*b.sc-1ll*a.sc*b.fs;
return {cr,(__int128)(a.fs+b.fs)*cr,(__int128)(a.sc+b.sc)*cr};
}
node query(int l,int r){
if(l<r)return pre[r]-pre[l-1];
else return pre[n]-pre[l-1]+pre[r];
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d%d",&p[i].fs,&p[i].sc);
for(int i=1;i<=n;i++){
int nxt=(i==n?1:i+1);
pre[i]=pre[i-1]+calc(p[i],p[nxt]);
}
while(q--){
int u,v;
scanf("%d%d",&u,&v);
int vsub1=(v==1?n:v-1);
node res=query(u,vsub1)+calc(p[v],p[u]);
double a2=res.cross;
printf("%.9lf %.9lf\n",(double)res.tx/(3.0*a2),(double)res.ty/(3.0*a2));
}
}
/*
*/
|
:::
G Cascading Grid
显然在同一行内左右相邻的非 # 构成一个连通块，选一个就必须选剩下所有，不妨缩到一起。
然后如果存在一个连通块 $u$ 能够通过题中所示操作到达 另一个连通块 $v$，则选 $u$ 必选 $v$。
猜你想找：最大闭合子图。随便抄个板子扔上去就行了。
:::info[code]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include<bits/stdc++.h>
#include<atcoder/maxflow>
#define pb push_back
using namespace std;
using namespace atcoder;
constexpr int inf=0x3f3f3f3f;
vector<string>s;
vector<int>id[35];
vector<int>val;
int cnt=0;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int h,w;
cin>>h>>w;
for(int i=0;i<h;i++){
string t;
cin>>t;
s.pb(t);
for(int j=0;j<w;j++)id[i].pb(-1);
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(s[i][j]!='#'&&id[i][j]==-1){
int tj=j,tval=0;
while(tj<w&&s[i][tj]!='#'){
id[i][tj]=cnt;
if(s[i][tj]=='+')tval++;
else tval--;
tj++;
}
val.pb(tval);
cnt++;
j=tj-1;
}
}
}
int yuan=cnt,hui=cnt+1;
mf_graph<int>g(cnt+2);
int maxv=0;
for(int i=0;i<cnt;i++){
if(val[i]>0){
maxv+=val[i];
g.add_edge(yuan,i,val[i]);
}else if(val[i]<0)g.add_edge(i,hui,-val[i]);
}
for(int i=0;i<h-1;i++)for(int j=0;j<w;j++)if(s[i][j]!='#'&&s[i+1][j]!='#')g.add_edge(id[i+1][j],id[i][j],inf);
cout<<maxv-g.flow(yuan,hui);
}
|
:::