文章目录

• 前言
• A MAX
• B PATH（已AC）
• C SQUARE
• D POLY (已AC)
• E PREVIEW
• F STRING（已AC）
• G REV
• H TRAVEL（已AC）
• I TREE
• J 大富翁（已AC）
• K 真假英雄（已AC）
• 总结

---

前言

说说这次比赛，参加队伍1947队，本队排名300+，自己确实有点菜了（队友表示不背锅）但是代码和题目的质量还是很高的（小声bb）。
**本次比赛一共AC六道题，消耗N根百年秀发（请允许我心疼自己几秒钟）。
A题请各大佬高抬贵手饶了小菜鸡，全场0.4%的准确率侧面反映那是巨佬互殴的题（我直接跳过此题）
B题使用的是stl库+dfs
C题。。。。
D题用的是数学思想+vector
E题。。。。
F题划水题本小菜鸡的最爱，无需算法，请直接看代码。
G题。。。。
H题使用的是分层最短路思想（属于板子题），还有一种解法可以使用DP+dij思路去解答。不过没去写，考场的时间不够（为自己不想去写别的代码正名）
I题。。。。
J题 又是小菜鸡的最爱，请大佬们直接看代码。
K题使用的是并查集思路 （让我勾起心痛的回忆，所以此题是队友写的）。
说了这么多 都是对题目简单分析和寻找方法，具体是实现请看我的代码。
感谢大家观看。
**
提示：以下是小菜鸡和大佬共同代码，均为原创，搬运代码请标明出处。

A MAX

B PATH（已AC）

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define int long long
#define Fast  ios::sync_with_stdio(false); cin.tie(0);	cout.tie(0); 
#define rep(i, a, b) for(int i = a; i <= (b); ++i)
#define per(i, b, a) for(int i = b ; i >= a; i--)
#define repn(i, a, b, n) for(int i = a; i <= (b); i+=n)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define int long long
using namespace std;
const int N = 120010;
int n, m;
struct edge {
	int y, nex, c;
}s[N * 8];
string ch[210];
bool tf[210][210];
int first[N], head[N], len = 1, tot, bg, ed, op, d[N], o;
int fx[4] = { -1,1,0,0 };
int fy[4] = { 0,0,-1,1 };
queue<int> q;
void ins(int x, int y, int c) {
	s[++len] = { y,first[x],c }; first[x] = len;
	s[++len] = { x,first[y],0 }; first[y] = len;
}
int pos(int x, int y) {
	return (x - 1) * m + y;
}
bool bfs() {
	memset(d, 0, sizeof(d)); d[bg] = 1;
	q.push(bg);
	for (int i = 1; i <= ed; i++) first[i] = head[i];
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int i = first[x]; i != 0; i = s[i].nex) if (!d[s[i].y] && s[i].c) {
			d[s[i].y] = d[x] + 1;
			q.push(s[i].y);
		}
	}
	return d[ed] != 0;
}
int dfs(int x, int t) {
	if (x == ed) return t;
	int tot = 0;
	for (int& i = first[x]; i != 0; i = s[i].nex) if (s[i].c && d[s[i].y] == d[x] + 1) {
		int my = dfs(s[i].y, min(t - tot, s[i].c));
		s[i].c -= my; s[i ^ 1].c += my; tot += my;
		if (t == tot) break;
	}
	return tot;
}
int dinic() {
	int dx = 0, ans = 0;
	while (bfs()) {
		dx = dfs(bg, 1e9);
		while (dx) ans += dx, dx = dfs(bg, 1e9);
	}
	return ans;
}
void input(){
	cin>>n;
	m = n;
	o = 3 * n * m; bg = o + 1; ed = o + 2;
	rep(i,1,n) {
		cin>>ch[i];
		ch[i]=" "+ch[i];
	}
	return;
}
void solve(){
	input();
	rep(i,1,n){
		rep(j,1,m){
		 	if (ch[i][j] == 'P') {
				tot++;
				if (ch[i][j + 1] == 'P') {
					tot--;
					ins(pos(i, j), n * m + pos(i, j), 1e9);
					ins(pos(i, j + 1), n * m + pos(i, j), 1e9);
					ins(n * m + pos(i, j), ed, 1);
				}
				if (ch[i + 1][j] == 'P') {
					tot--;
					ins(2 * n * m + pos(i, j), pos(i, j), 1e9);
					ins(2 * n * m + pos(i, j), pos(i + 1, j), 1e9);
					ins(bg, 2 * n * m + pos(i, j), 1);
				}
			}			
		}
	}
	rep(i,1,ed) head[i] = first[i];
	cout<<dinic()+tot;
	return;
}
signed main(void) {
	Fast;
	solve();
	return 0;
}

C SQUARE

D POLY (已AC)

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
	int x,y,D;
}point;
vector<point> P;
const int N = 5e3+10;
int C,n;
bool xpow(int a,int b,int c,int d){
	return a*b-c*d;
}
int cal(int a,int b,int c,int d){
	return (a-b)*(a-b)+(c-d)*(c-d);
}
void solve(){
	cin>>C;
	if (C%2==1){
		cout<<-1;
		return ;
	}
	int M=C/2;
	int Ma,Mi,x,dis;
	for (int i=1;i<=C;i++){
		for (int j=0;i*i+j*j<=M*M;j++){
			x=i*i+j*j;
			dis=sqrt(x);
			if (dis*dis==x) P.push_back({i,j,dis});
		}	
	}
	int ans=N;
	for (auto p : P){
		for (auto q : P){
			x=cal(p.x,q.x,p.y,q.y);
			dis=sqrt(x);
			if (dis*dis==x&&xpow(p.x,q.y,p.y,q.x)&&dis+p.D+q.D==C){
				Ma=max(dis,max(p.D,q.D));
				Mi=min(dis,min(p.D,q.D));
				ans=min(ans,Ma-Mi);
			}
		}		
	}
	if (ans!=N) cout<<ans;
	else cout<<M%2;
	return;
}
int main(void){
	solve();
	return 0;
}

E PREVIEW

F STRING（已AC）

#include<stdio.h>
const int N =1e6+10;
char a[N],b[N];
 
int main(void){
    int n,p,cnt=0;
    scanf("%d",&n);
    scanf("%s%s",&a,&b);
    p=n-1;
    for(int i=n-1;i>=0;i--){
        if(a[i]==b[p]) p--;
    }
    printf("%d",p+1);
    return 0;
}

G REV

H TRAVEL（已AC）

#include <iostream>
#include <cstring>
#include <queue>
#define FAST     ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
const int N=2e5+10,M=2e5+10,INF=0x3f3f3f3f;
int tot,K,s,t,n,m;
int head[N],d[N][5];
struct Edge{
    int to,len,nex;
}edge[M<<1];
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>q;
void add(int from,int to,int len){
    edge[++tot]=(Edge){to,len,head[from]};head[from]=tot;
    edge[++tot]=(Edge){from,len,head[to]};head[to]=tot;
}
void dij()
{
    while(!q.empty()) q.pop();
    memset(d,INF,sizeof(d));
    q.push(make_pair(0,make_pair(s,0))),d[s][0]=0;
    while(!q.empty())
    {
        int x=q.top().second.first,k=q.top().second.second;q.pop();
        for(int i=head[x];i;i=edge[i].nex)
        {
            int y=edge[i].to,l=edge[i].len;
            if(d[x][k]+l<d[y][k])     
            {
                d[y][k]=d[x][k]+l;
                q.push(make_pair(d[y][k],make_pair(y,k)));
            }
            if(k+1<=K&&d[x][k]<d[y][k+1])     
            {
                d[y][k+1]=d[x][k];
                q.push(make_pair(d[y][k+1],make_pair(y,k+1)));
            }
        }
    }
}
void input_1(){
    cin>>n>>m>>K;
    return;
}
void create(){
    int a,b,c;
    cin>>a>>b>>c;
    add(a,b,c);
    return;
}
void solve(){
    input_1();
  	s=1,t=n;
    while(m--) create();
    dij();
    int ans=INF;
    for(int i=0;i<=K;i++) {
        if(d[t][i]<ans) ans=d[t][i];
        else continue;
    }
    cout<<ans<<endl; 
}
int main(void){
    FAST;
    solve();
    return 0;
}

I TREE

J 大富翁（已AC）

#include<stdio.h>
int main(void){
  int a,n,max_=1;
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    int a;
    scanf("%d",&a);
    if(max_<i) {
      printf("%d",max_);
      return 0;
    }
    if(a+i>max_) max_=a+i;
  }
  printf("%d",max_);
  return 0;
}

K 真假英雄（已AC）

#include<iostream>
#include<cstring>

using namespace std;
const int N = 1e6 + 5;
int fa[N], Size[N], n, m, ans;
int read() {
	int x = 0, w = 1; char ch = getchar();
	while (ch > '9' || ch < '0') { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();
	return x * w;
}

int find(int x) {
	if (fa[x] == x)return fa[x];
	fa[x] = find(fa[x]);
	Size[fa[x]] += Size[x];
	Size[x] = 0;
	return fa[x];
}

void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	if (fx != fy) {
		Size[fx] += Size[fy]; Size[fy] = 0;
		fa[fy] = fx;
	}
}
//以上是并查集 
int main() {
	n = read(); m = read(); ans = 0;
	for (int i = 1; i <= 2 * n; i++)fa[i] = i;
	for (int i = 1; i <= n; i++)Size[i] = 0;
	for (int i = 1 + n; i <= 2 * n; i++)Size[i] = 1;//预处理 
	for (int i = 1; i <= m; i++) {
		int x = read(), y = read();
		int fx = find(x), fy = find(y), fxn = find(x + n), fyn = find(y + n);//假定x,y表示坏人，x+n,y+n表示好人 
		string ch; cin >> ch;
		if (ch == "good") {
			merge(x,y); merge(x+n,y+n);//如果x说y是好人，则x,y要么同时是好人，要么同时是坏人 
		}
		else {
			merge(x,y+n); merge(x+n,y);//如果x说y是坏人，则x,y一定有一好一坏的情况 
		}
	}
	for (int i = 1; i <= n; i++) {
		if (find(i) == find(i + n)) { cout << -1 << endl; return 0; }//如果出现了i既是好人又是坏人的情况，则无解 
	}
	for (int i = 1; i <= n; i++) {
		ans += max(Size[find(i)], Size[find(i + n)]);//统计答案 ,取max是因为贪心取最大就好，因为两个不同条件的成立带来的影响是不一样的 
		Size[find(i)] = Size[find(i + n)] = 0;//注意清0，因为之前已经统计过答案了 
	}cout << ans << endl;
	return 0;
}

总结

这类比赛带来最大的感受是 自己还是需要好好学习，离大佬的差距还有很多。写这个博客也算是纪念一下这次比赛吧！这次夏季赛也给本人带来很多收获，有被92院校大佬认可组队的喜悦和西电拿ACM-ICPC银的大佬日常帮助解答疑惑的感动，感谢本次比赛给自己带来的成长。再次感谢大家能看我写的文章。