Codeforces Round 1006 (Div. 3)

比赛链接: https://codeforces.com/contest/2072

唉唉，有点菜了。

上课vp的，F vp结束半小时才ac。每题都写太慢了。。。

A

$k$ 是正数或者负数是没有什么不一样的，所以直接让 $k$ 一直为正数就好了。然后其实就是直接输出 $\frac{k}{p}$ 向上取整就好了。

cpp

void solve() {
	int n,k,p;
	cin>>n>>k>>p;
	k=abs(k);
	int ans=(k-1)/p+1;
	if(k==0) ans=0;
	cout<<(ans>n?-1:ans)<<'\n'; 
}

我赛时写的有点唐。

cpp

void solve() {
	int n,k,p;
	cin>>n>>k>>p;
	if(!k) {
		cout<<"0\n";
		return;
	}
	int sum=0;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=p; j++) {
			if(sum<=k) break;
			sum--;
		}
		for(int j=1; j<=p; j++) {
			if(sum>=k) break;
			sum++;
		}
		if(sum==k){
			cout<<i<<"\n";
			return;
		}
	}
	cout<<"-1\n";
}

B

对于每一个 _ ，它的贡献是它前面的 _ 的数量乘它后面的 _ 的数量。我们可以简单的想到，把一个数拆成两个数，使得它们的乘积最大，那么这两个数一定是要尽量相等。

所以我们重新排列的字符串，肯定是 _ 全部放中间，前面后面的 - 各放一半。

cpp

void solve()
{
	int n;
	string s;
	cin>>n>>s;
	int x=count(s.begin(),s.end(),'_');
	if((n-x)&1){
		cout<<1LL*(n-x)/2*((n-x)/2+1)*x<<'\n';
	}else{
		cout<<1LL*(n-x)/2*(n-x)/2*x<<'\n';
	}
}

C

数组的 $M E X$ 如果要达到 $x$ 那么一定会有 $[0, x - 1]$ 之间的每一个数字。由于数组 $a$ 按位或要等于 $x$ ，每个数字每一位只有在 $x$ 为 $1$ 的位才能为 $1$ 。

我们直接从 $[0, n]$ 开始尝试能不能把 $i$ 加入数组，如果不行，那么可以直接不用看后面的数了，因为数组里不可能有 $i$ 了， $M E X$ 只能为 $i$ ，就没必要看其他的数字了，如果可以就加入答案中。

在上一步循环结束后，我们添加的数字个数一定小于等于 $n$ 。如果小于 $n$ ，那么我们可以往里面放 $x$ ，这样它们按位或一定会等于 $x$ 。如果等于 $n$ ，那么需要检查它们按位或能不能等于 $x$ ，不行则把最大的一个数字换成 $x$ 。

cpp

void solve() {
	int n,x;
	cin>>n>>x;
	vector<int>ans;
	int now=0;
	for(int i=0; i<n; i++) {
		if((i|x)==x) ans.push_back(i);
		else break;
		now|=i;
	}
	while(ans.size()==n&&now!=x)
		ans.pop_back();
	if(ans.size()<n){
		while(ans.size()<n)
			ans.push_back(x);
		now|=x;
	}
	//assert(now==x);
	for(auto y:ans)
		cout<<y<<' ';
	cout<<'\n';
}

D

只能做一次操作，可以把一个数字 $a_{l}$ 移动到 $a_{r}$ 的后面，要使得操作之后，数组中的逆序对最少。

计算 $i$ 移动到 $j$ 会使逆序对增加/减少多少。然后 $i$ 移动到 $j + 1$ , 是可以通过移动到 $j$ 的答案算出来的。

贴一下 jiangly 的代码。~~非常的简洁啊，我确实没想到这种正常的做法...~~

cpp

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            sum += (a[i] < a[j]);
        }
    }
    
    int ans = sum;
    int l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        int cur = sum;
        for (int j = i + 1; j < n; j++) {
            cur -= (a[i] > a[j]);
            cur += (a[i] < a[j]);
            if (cur < ans) {
                ans = cur;
                l = i;
                r = j;
            }
        }
    }
    std::cout << l + 1 << " " << r + 1 << "\n";
}

我这做法太麻烦了。

由于数据很小，可以直接枚举每一对可能的交换，然后计算最大的贡献。把 $a_{l}$ 移动到 $a_{r}$ 的后面，会让答案减去 $[l + 1, r]$ 之间小于 $a_{l}$ 的数字的数量，加上 $[l + 1, r]$ 之间大于 $a_{l}$ 的数字的数量。

计算每一个区间的贡献，然后选出使答案减少最多的。

可以用前缀和预处理出每个前缀比 $i$ 小的数字的数量。

cpp

constexpr int N = 2000;

void solve() {
	int n;
	cin>>n;
	vector<int>a(n+1);
	vector<vector<int>>cnt(n+1,vector<int>(N+1)),tnc(n+1,vector<int>(N+1));
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		cnt[i]=cnt[i-1];
		tnc[i]=tnc[i-1];
		for(int j=a[i]+1; j<=N; j++)
			cnt[i][j]++;//前面的比它小的数字
		for(int j=1; j<a[i]; j++)
			tnc[i][j]++;
	}
	auto calc=[&](int i,int j) {
		int res=0;
		res+=tnc[j][a[i]]-tnc[i][a[i]];//[i,j]之间的比a[i]大的数字
		res-=cnt[j][a[i]]-cnt[i][a[i]];
		return res;
	};
	vector<array<int,3>>ans;
	for(int i=1; i<=n; i++) {
		for(int j=i+1; j<=n; j++) {
			ans.push_back({i,j,calc(i,j)});
		}
	}
	sort(ans.begin(),ans.end(),[](array<int,3>x,array<int,3>y) {
		return x[2]<y[2];
	});
	if(ans.empty()||ans[0][2]>0)
		cout<<"1 1\n";
	else
		cout<<ans[0][0]<<" "<<ans[0][1]<<'\n';
}

E

稍微推一下或者想一下就能发现，满足条件的点对一定是 $x$ 相同或者 $y$ 相同。但是注意 $n$ 是有限制的，且比较小。

所以我们需要让有的水平的线上点尽量的多。

但是之后的也要考虑不要和它们横坐标或纵坐标相同。

其实可以递归，感觉会比较好看。

cpp

void solve()
{
	int k;
	cin>>k;
	if(!k){
		cout<<"0\n";
		return;
	}
	int X=1,Y=1;
	vector<pair<int,int>>ans;
	auto work=[&](int cnt){
		int sum=1;
		int x=2;
		ans.push_back({X,++Y});
		ans.push_back({X,++Y});
		while(sum+x<cnt){
			sum+=x;
			x++;
			ans.push_back({X,++Y});
		}
		++X,Y+=2;
		return sum;
	};
	int now=0;
	while(now<k){
		now+=work(k-now);
	}
	cout<<ans.size()<<'\n';
	for(auto it:ans)
		cout<<it.first<<" "<<it.second<<'\n';
}

F

直接打表找规律，发现大小为2，4，8，16这些的三角形，都是由三个大小为它们二分之一的三角形拼成的，中间部分都是0。

然后就可以直接DFS了，当然还有其他很简单的方法，但是DFS也挺好写的。

cpp

int val;
vector<int>dfs(int k)
{
	if(k==1){
		return {0,val};
	}
	vector<int>res(k+1);
	int x=k-(1<<__lg(k));
	if(!x) x=k>>1;
	vector<int>nxt=dfs(x);
	for(int i=1;i<=x;i++)
		res[i]=nxt[i];
	auto it=nxt.rbegin();
	for(int i=k,j=x;i>=k-x+1;i--,j--)
		res[i]=nxt[j];
	return res;
}
void solve()
{
//	vector<vector<char>>a(100,vector<char>(100));
//	for(int i=1;i<=99;i++)
//		for(int j=1;j<=i;j++){
//			if(j==1||j==i) a[i][j]='k';
//			else{
//				if(a[i-1][j-1]==a[i-1][j])
//					a[i][j]='0';
//				else
//					a[i][j]='k';
//			}
//			cout<<a[i][j]<<" \n"[j==i];
//		}
	//every triangle consists of 3 small one ,and the center part are all 0
	//for example,if n=7:
	//size 8 triangle consists of 3 4-size triangle
	//so the problem is to find 3-size trangle
	//*
	//** so k0k k0k 0 k0k
	int k;
	cin>>k>>val;
	vector<int>res=dfs(k);
	for(int i=1;i<=k;i++)
		cout<<res[i]<<" \n"[i==k];
}

G

对于 $p \leq \sqrt{n}$ 的部分，直接求解。

对于 $\sqrt{n} < p \leq n$ 的部分， $n$ 的 $p$ 进制有且仅有2位数字。

低位是 $n$ mod $p$ = $n-p \cdot \lfloor \frac{n}{p} \rfloor $ , 高位是 $⌊ \frac{n}{p} ⌋$ .

此时 $rev(n,p) = $ $p (n - p \cdot ⌊ \frac{n}{p} ⌋) + ⌊ \frac{n}{p} ⌋ = p n - p^{2} ⌊ \frac{n}{p} ⌋ + ⌊ \frac{n}{p} ⌋$

对于 $i$ ，最后一个满足 $\lfloor\frac{n}{j}\rfloor= $ $⌊ \frac{n}{i} ⌋$ 的 $j$ 是 $⌊ \frac{n}{⌊ \frac{n}{i} ⌋} ⌋$ .

因为当 $⌊ \frac{n}{i} ⌋ = k$ 时， $k \le \lfloor\frac{n}{i}\rfloor < k+1 $ ，可以变形为 $\frac{n}{k + 1} < i \leq \frac{n}{k}$ ，所以满足条件的最大整数即为 $⌊ \frac{n}{k} ⌋$ .

那么 $[i, j]$ 这一段的 $⌊ \frac{n}{p} ⌋$ 都是相等的。

整了好久样例都不对，然后看了眼题目发现mod取错了。。。。

cpp

#include <bits/stdc++.h>
using namespace std;

// #define int long long
constexpr int N = 3e5;
// constexpr int mod = 998244353;
constexpr int mod = 1e9 + 7;
//六百六十六 mod 取错了。。。

vector<long long> s1(N + 1);

void solve()
{
    int n;
    long long k;
    cin >> n >> k;
    // pn-p*p*(n/p)+n/p
    long long ans = 0;
    if (k > n) {
        ans += ((k - n) % mod) * n % mod;
        k = n;
    }
    for (int i = 2; i <= k; i++) {
        if (1LL * i * i <= n) {
            vector<int> v;
            int x = n;
            while (x) {
                v.push_back(x % i);
                x /= i;
            }
            for (auto j : v)
                x = x * i + j;
            ans = (ans + x) % mod;
        } else {
            int L = i;
            auto calc = [](int l, int r) {
                return 1LL * (r - l + 1) * (l + r) / 2 % mod;
            };
            while (L <= k) {
                int R = n / (n / L);
                if (R > k)
                    R = k;
                ans = (ans - ((s1[R] - s1[L - 1]) % mod) * (n / L) % mod) % mod;
                ans = (ans + 1LL * calc(L, R) * n % mod) % mod;
                ans = (ans + 1LL * (R - L + 1) * (n / L) % mod) % mod;
                ans = (ans + mod) % mod;

                L = R + 1;
            }
            break;
        }
    }
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    for (int i = 1; i <= N; i++)
        s1[i] = (s1[i - 1] + 1LL * i * i % mod) % mod;
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Codeforces Round 1006 (Div. 3)

Codeforces Round 1006 (Div. 3) ​

A ​

B ​

C ​

D ​

E ​

F ​

G ​

Codeforces Round 1006 (Div. 3)

A

B

C

D

E

F

G