一场打崩的\(Div \space 2\)

从 \(C\) 开始吧

C.Eugene and an array

我自己做的时候发现：啊，正难则反呀

然后就推不出来了

我们发现哪些区间是好的呢？

用 \(map\) 统计前缀和上一次出现的位置，\(rpos\) \(-\) \(lpos\) 统计答案即可

真的是晕了

\(Code :\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
		return res*f;
	}
	const int N=3e5+10;
	int a[N],n,ans;
	map<int,int> mp;
	signed main()
	{
		n=read(); for(int i=1;i<=n;++i) a[i]=read()+a[i-1];
		int l=0; mp[0]=0;
		for(int i=1;i<=n;++i)
		{
			if(mp.count(a[i])) l=max(l,mp[a[i]]+1);
			ans+=i-l; mp[a[i]]=i;
		}cout<<ans<<endl;
		return 0;
	}
}
signed main(){return yspm::main();} 

D.Challenges in school №41

没有理解题意，然后就废了，觉得就是个模拟题，然后却没有过

我们统计逆序对个数和我们进行冒泡排序的最小的轮数

如果这个给定的轮数没有在这个区间之内，那就肯定 \(-1\) 了

审题的关键点：每一轮孩子们不一定都要全部转头的

剩下就是个模拟题，有不少的细节

\(Code:\)

#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm {
inline int read() {
    int res = 0, f = 1;
    char k;
    while (!isdigit(k = getchar()))
        if (k == ‘-‘)
            f = -1;
    while (isdigit(k)) res = res * 10 + k - ‘0‘, k = getchar();
    return res * f;
}
const int N = 5010;
int n, k, maxx, minn, a[N], b[N], sum[N];
char s[N];
vector<int> vec[N];
signed main() {
    n = read();
    k = read();
    scanf("%s", s + 1);
    for (int i = 1; i <= n; ++i) b[i] = s[i] == ‘R‘;
    for (int i = 1; i <= n; ++i) {
        int cnt = 0;
        for (int j = 1; j < n; ++j) {
            if (b[j] > b[j + 1])
                cnt++, vec[i].push_back(j);
        }
        for (int j = 0; j < cnt; ++j) {
            swap(b[vec[i][j]], b[vec[i][j] + 1]);
        }
        if (!cnt) {
            minn = i - 1;
            break;
        }
        maxx += cnt;
        sum[i] = sum[i - 1] + cnt;
    }
    if (k < minn || k > maxx)
        return puts("-1"), 0;
    if (k == minn) {
        for (int i = 1; i <= minn; ++i) {
            printf("%lld ", (int)vec[i].size());
            int len = vec[i].size();
            for (int j = 0; j < len; ++j) printf("%lld ", vec[i][j]);
            puts("");
        }
        return 0;
    }
    int now = 0;
    while (now < minn && maxx - sum[now + 1] + now + 1 >= k) ++now;
    for (int i = 1; i <= now; ++i) {
        int sz = vec[i].size();
        printf("%lld ", sz);
        for (int j = 0; j < sz; ++j) printf("%lld ", vec[i][j]);
        puts("");
    }
	if (maxx - sum[now] + now - k + 1  ) {
        printf("%lld ", maxx - sum[now] + now - k + 1);
        for (int i = 0; i < maxx - sum[now] + now - k + 1; ++i) printf("%lld ", vec[now + 1][i]);
        puts("");
    }
    int sz = vec[now + 1].size();
    for (int i = maxx - sum[now] + now - k + 1; i < sz; ++i) printf("%lld %lld\n", 1ll, vec[now + 1][i]);
    for (int i = now + 2; i <= minn; ++i) {
        int sz = vec[i].size();
        for (int j = 0; j < sz; ++j) printf("%lld %lld\n", 1ll, vec[i][j]);
    }
    return 0;
}
}  // namespace yspm
signed main() { return yspm::main(); }

E.Road to 1600

见人见智的构造题

考虑我们不可能搞出来一个矩阵递推式或者类似的东西，所以肯定是部分构造，大块找规律

我们发现如下的 \(3 \times 3\) 的矩阵是满足条件的

构造方式不止这一种

本题目的最大难度就是在这里了

其实可以打一个深搜做一下

剩余的部分就直接蛇形填数就好了，从\(1 \rightarrow (n-9)\)

剩下的九个数按照那个矩阵的大小关系进行分布就可以了

正确性验证即可

\(Code:\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar(); 
		return res*f;
	}
	const int N=510;
	int ans[N][N]; 
	signed main()
	{
		int n=read();
		if(n<=2) return puts("-1"),0;
		int cnt=0;
		for(int i=n;i>3;--i)
		{
			if((n-i)&1)
			{
				for(int j=1;j<=i;++j) ans[i][j]=++cnt;
				for(int j=i-1;j>=1;--j) ans[j][i]=++cnt;
			}
			else
			{
				for(int j=1;j<=i;++j) ans[j][i]=++cnt;
				for(int j=i-1;j>=1;--j) ans[i][j]=++cnt;
			}
		}
		ans[3][1]=++cnt; ans[2][2]=++cnt; ans[3][2]=++cnt;
		ans[3][3]=++cnt; ans[1][2]=++cnt; ans[1][3]=++cnt;
		ans[2][1]=++cnt; ans[2][3]=++cnt; ans[1][1]=++cnt;
		for(int i=1;i<=n;++i) 
		{
			for(int j=1;j<=n;++j) cout<<ans[i][j]<<" "; cout<<endl;
		}
		return 0;
	}
}
signed main(){return yspm::main();}

F.Kate and imperfection

这题真的难懂诶

赛后看题还得看半天

往集合里面放的时候首先放素数（这个显然）

然后我们把答案定为 \(2\)， 发现集合里面可以有 \(4\)

然后定为 \(3\) 可以加入 \(6,9\)

其实就是\(2 \times ans \rightarrow ans \times ans\)

那么每个数字被加入集合的时候它的 除本身因子 已经被钦定为答案了

所以我们找到每个数字的最大真因子，\(sort\) 答案 输出即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar(); 
		return res*f;
	}
	const int N=5e5+10;
	int a[N],cnt[N]; 
	signed main()
	{
		int n=read();
		for(int i=1;i<=n;++i) for(int j=2;j<=n/i;++j) a[i*j]=i;
		for(int i=1;i<=n;++i) cnt[a[i]]++;
		for(int i=1;i<=n;++i) while(cnt[i]--) printf("%lld ",i); puts(""); 
		return 0;
	}
}
signed main(){return yspm::main();}

Codeforces Round#632 Div2 解题报告

原文：https://www.cnblogs.com/yspm/p/12672320.html