前言

周赛0题，1/3都看过还做过，还有一道题反复做过，太难受了

一、我在哪？

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
using namespace std;

const int maxx = 1e4 + 5;
const int maxn = 1e6 + 5;

#define N 10000100
#define ll long long
#define endl '\n'
const ll limit = 2000000;
const ll  mod = 998244353;
#define test printf("--------------------------\n");
//#define p printf
//#define s scanf
#define re(a) memset((a), 0, sizeof((a)))
#define remax(a) memset((a), 0x3f3f3f3f, sizeof((a)))

int main() {
	IOS;
	int n;
	cin >> n;
	string s;
	cin >> s;
	for (int i = 1; i <= n; ++i) {
		set<string> se;
		se.clear();
		bool flag = true;
		int j;
		for (j = 0; j + i <= n; ++j) {
			string t = s.substr(j, i);
			se.insert(t);
		}
		if (se.size() == j) {
			cout << i << endl;
			break;
		}
		/*1.	string temp = s.substr(j, i);
				if (se.count(temp) > 0) {//优化,寻找容器里有没有temp
					flag = false;
					break;
				}
				se.insert(temp);
			}
			if (flag) {
				cout << i;
				return 0;
			}*/
		/*2.if(se.size() == n - i + 1){//看图，因为刚好不重复的那个长度就有
				cout << i << endl;
				return 0;
		}
	}*/
	return 0;
}

这里需要注意的是可以用set容器的自动去重去查找有没有一样的字符串，没有就可以直接输出了

比较相似的题：Prefix Removals
这是通过证明在什么时刻，才会有不再重复的情况

二、股票买卖

读了几遍都读错了，我读题老是会错题，一定要改改
读错的点：当天卖了，下一天才能买
就是纯纯的贪心嘛

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <stack>
#define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
using namespace std;

const int maxx = 1e4 + 5;
const int maxn = 1e6 + 5;

#define N 10000100
#define ll long long
#define endl '\n'
const ll  mod = 998244353;
#define test printf("--------------------------\n");
#define re(a) memset((a), 0, sizeof((a)))
#define remax(a) memset((a), 0x3f3f3f3f, sizeof((a)))

inline int read () {
	int s = 0, w = 1;
	char ch = getchar ();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			w = -1;
		ch = getchar ();
	}
	while (ch >= '0' && ch <= '9')
		s = s * 10 + ch - '0', ch = getchar ();
	return s * w;
}

int a[maxn];
int dp[maxn];

int main() {
	IOS;
	// freopen("P1908_6.in","r",stdin);//读入数据
	// freopen("P1908.out","w",stdout); //输出数据

	int n;
	cin >> n;
	ll sum = 0, ans = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for (int i = 2; i <= n; ++i) {
		if (a[i] - a[i - 1] > 0)
			ans += (a[i] - a[i - 1]);//画个线图
	}
	cout << ans;
	return 0;
}

类似题：能量石

三、序列处理

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include<cmath>
#include<stack>
#define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
using namespace std;

const int maxx = 1e4 + 5;
const int maxn = 1e6 + 5;

#define N 10000100
#define ll long long
#define endl '\n'
const ll  mod = 998244353;
#define test printf("--------------------------\n");
#define re(a) memset((a), 0, sizeof((a)))
#define remax(a) memset((a), 0x3f3f3f3f, sizeof((a)))

inline int read () {
	int s = 0, w = 1; char ch = getchar ();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar ();}
	while (ch >='0' && ch <= '9') s = s*10 + ch-'0', ch = getchar ();
	return s * w;
}

int a[3010];

//我的想法是还没到你但你也得腾位置出来给那同一个数，标答想法是一个一个腾位置，没到你就不挪

int main() {
	IOS;
	// freopen("P1908_6.in","r",stdin);//读入数据
	// freopen("P1908.out","w",stdout); //输出数据
	int n;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    int ans = 0;
    a[0] = 0;
    for (int i = 1, last = 0; i <= n; ++i){
        int temp = max(a[i - 1] + 1, a[i]);
        ans += temp - a[i];
        a[i] = temp;
        last = temp;
    }
    cout << ans;
    return 0;
}

相似题：修改数组

int a[maxn];
int p[maxn];

int find(int x){
    if(p[x] == x) return x;
    return p[x] = find(p[x]);
}

int main() {
	IOS;
	// freopen("P1908_6.in","r",stdin);//读入数据
	// freopen("P1908.out","w",stdout); //输出数据
	int n;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    for(int i = 1; i <= maxn; ++i) p[i] = i;
    for (int i = 1; i <= n; ++i){
        int temp = find(a[i]);
        if(a[i] != temp) a[i] = find(a[i]);
        cout << a[i] << ' ';
        p[a[i]] = a[i] + 1;
    }
    return 0;
}

这道题

四、鸣人的影分身

是整数划分的变形题
在洛谷找到:（不是板子题哈）
集合划分计数
 整数划分
 数的划分类似于板子，0不能填进去时的情况

整数划分结论：（3，3，1 和 1，3，3这类是一样的不计入其中）
q (n, m) = 1 (n == 1 || m == 1)
q (n, m) = q (n, n) (n < m) （只含n和不含n的所有n-1划分）
q (n, m) = 1 + q (n, m - 1) (n == m)
q (n, m) = q (n - m, m) + q (n, m - 1) (n > m) (含m和不含m时n的m-1划分)

对比了下这道题的状态转移方程是差不多的哈，这题就是个板子题
这题爆搜也能做，dfs题解
道理是一样的，上面那个结论

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include<cmath>
#include<stack>
#define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
using namespace std;

const int maxx = 1e4 + 5;
const int maxn = 1e6 + 5;

#define N 10000100
#define ll long long
#define endl '\n'
const ll  mod = 998244353;
#define test printf("--------------------------\n");
#define re(a) memset((a), 0, sizeof((a)))
#define remax(a) memset((a), 0x3f3f3f3f, sizeof((a)))

inline int read () {
	int s = 0, w = 1; char ch = getchar ();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar ();}
	while (ch >='0' && ch <= '9') s = s*10 + ch-'0', ch = getchar ();
	return s * w;
}

int dp[20][20], a[20];

int main() {
	IOS;
	// freopen("P1908_6.in","r",stdin);//读入数据
	// freopen("P1908.out","w",stdout); //输出数据
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> m >> n;
        re(dp);
        dp[0][0] = 1;//00是一种方案
        for(int i = 0; i <= m; ++i){
            for(int j = 1; j <= n; ++j){
                dp[i][j] = dp[i][j - 1];//上一个的数字方案个数（比如这次是4位，上次就是3位）
                if(i >= j) dp[i][j] += dp[i - j][j];
            }
        }
        cout << dp[m][n] << endl;
    }
    return 0;
}
//-----------------------------------------------------dfs
int dfs(int sum, int start){
    if(sum == 0)
        return 1;
    if(start == 0)
        return 0;
    if(sum == start)
        return 1 + dfs(sum, start - 1);
    if(sum > start)
        return dfs(sum - start, start) + dfs(sum, start - 1);
    if(start > sum)
        return dfs(sum, sum);
}

int main() {
	IOS;
	// freopen("P1908_6.in","r",stdin);//读入数据
	// freopen("P1908.out","w",stdout); //输出数据
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> m >> n;
        cout << dfs(m, n) << endl;
    }
    return 0;
}

五、家谱树

这居然是裸的拓扑排序，人傻了，果然对图掌握的可以说是基本没有
（acwing有，没报班看不了）
我不知道对没有，样例过了，有机会的话，或者你愿意的话交了给我说说吧
在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include<cmath>
#include<queue>
#include<stack>
#define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
using namespace std;

const int maxx = 1e4 + 5;
const int maxn = 1e6 + 5;

#define N 10000100
#define ll long long
#define endl '\n'
const ll  mod = 998244353;
#define test printf("--------------------------\n");
#define re(a) memset((a), 0, sizeof((a)))
#define remax(a) memset((a), 0x3f3f3f3f, sizeof((a)))

inline int read () {
	int s = 0, w = 1; char ch = getchar ();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar ();}
	while (ch >='0' && ch <= '9') s = s*10 + ch-'0', ch = getchar ();
	return s * w;
}

int in[105];
vector<int> v[105];
vector<int> ans;

int main() {
	IOS;
	// freopen("P1908_6.in","r",stdin);//读入数据
	// freopen("P1908.out","w",stdout); //输出数据
	int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int temp;
        while(cin >> temp && temp){
            ++in[temp];
            v[i].push_back(temp);
        }
    }
    queue<int> q;
    for (int i = 1; i <= n; ++i){
        if(in[i] == 0) {
            q.push(i);
        }
    }
    while(!q.empty()) {
        int t = q.front();
        q.pop();
        ans.push_back(t);

        for(auto w : v[t]){
            --in[w];
            if(in[w] == 0)
                q.push(w);
        }
    }
    for(auto w : ans){
        cout << w << " ";
    }
        return 0;
}

几个要素：
入度，入读为0的点反复加入知道没有能加的
queue vector关系 vector答案

最大食物链计数增加了对入度出度的考察

int in[maxn], out[maxn];
vector<int> v[maxn];
vector<int> ans;
int lu[maxn];//路径

int main() {
	IOS;
	// freopen("P1908_6.in","r",stdin);//读入数据
	// freopen("P1908.out","w",stdout); //输出数据
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int temp, ou;
		cin >> temp >> ou;
		++in[ou], ++out[temp];
		v[temp].push_back(ou);
	}
	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		if (in[i] == 0) {
			q.push(i);
			lu[i] = 1;
		}
	}
	while (!q.empty()) {
		int t = q.front();
		q.pop();
		ans.push_back(t);

		for (auto w : v[t]) {
			--in[w];
			lu[w] = (lu[w] + lu[t]) % 80112002;//加上上一个点被经过的路径
			if (in[w] == 0)
				q.push(w);
		}
	}
	int res = 0;
	for (int i = 1; i <= n; ++i) {
		if (out[i] == 0) {//去看题解为什么
			res = (res + lu[i]) % 80112002;
		}
	}
	cout << res;
	return 0;
}

先存着到时候看

六、Connect

嘿嘿知道了cf怎么搜题，就是直接改网址链接

一眼觉得是双端队列bfs
但是不是这个思路哈

这题居然是求出能到的没有代价的地方，暴力枚举所有点求一个最小值。
因为最多只能建一个通道，而且保证一定有解。

这里枚举所有点，还涉及到了曼哈顿距离那个定理，说白了就是折现和直线的距离是一样的

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include<cmath>
#include<stack>
#include<queue>
#define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
using namespace std;

const int maxx = 1e4 + 5;
const int maxn = 1e6 + 5;

#define N 10000100
#define ll long long
#define endl '\n'
const ll  mod = 998244353;
#define test printf("--------------------------\n");
#define re(a) memset((a), 0, sizeof((a)))
#define remax(a) memset((a), 0x3f3f3f3f, sizeof((a)))

inline int read () {
	int s = 0, w = 1; char ch = getchar ();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar ();}
	while (ch >='0' && ch <= '9') s = s*10 + ch-'0', ch = getchar ();
	return s * w;
}

int n, m;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
char g[55][55];
bool vis[55][55];

 
 vector<pair<int, int>> v, vv;

 void bfs(int x1, int y1)
 {
     queue<pair<int, int>> q;
     q.push({x1, y1});
     v.push_back({x1, y1});
     vis[x1][y1] = true;
     while (!q.empty())
     {
         pair<int, int> se = q.front();
         q.pop();

         for (int i = 0; i < 4; ++i)
         {
             int xx = se.first + dx[i];
             int yy = se.second + dy[i];

             if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && !vis[xx][yy] && g[xx][yy] == '0')
             {
                 vis[xx][yy] = true;
                 q.push({xx, yy});
                 v.push_back({xx, yy});
             }
         }
     }
    
}

void bbfs(int x1, int y1)
 {
     re(vis);
     queue<pair<int, int>> q;
     q.push({x1, y1});
     vv.push_back({x1, y1});
     vis[x1][y1] = true;
     while (!q.empty())
     {
         pair<int, int> se = q.front();
         q.pop();

         for (int i = 0; i < 4; ++i)
         {
             int xx = se.first + dx[i];
             int yy = se.second + dy[i];

             if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && !vis[xx][yy] && g[xx][yy] == '0')
             {
                 vis[xx][yy] = true;
                 q.push({xx, yy});
                 vv.push_back({xx, yy});
             }
         }
     }
    
}

int main(){
    IOS;
	// freopen("P1908_6.in","r",stdin);//读入数据
	// freopen("P1908.out","w",stdout); //输出数据
    cin >> n;
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> g[i][j];//这里不要cin>>g[i]， 错傻了怎么找都觉得没问题，最后居然是这里
    bfs(x1, y1);
    bbfs(x2, y2);
    int ans = 0x3f3f3f3f;
    for (int i = 0; i < v.size(); ++i){
        for (int j = 0; j < vv.size(); ++j){
            int temp = (v[i].first - vv[j].first) * (v[i].first - vv[j].first) + (v[i].second - vv[j].second) * (v[i].second - vv[j].second);
            ans = min(ans, temp);
        }
    }
    cout << ans << endl;
    return 0;
}