来自学长的推荐()

A. Set

还做过类似的题,但是真的忘了

发现该题特殊点在于有 \(n\) 个数,求能被 \(n\) 整除的,明明是两个看似无关的数据,却给了同一个值,那么这里就是解题的关键

我们维护前缀和,最多有 \(n\)种取值, 如果前缀和为 \(0\) 那么从一开始到这个位置就是一个合法解,所以我们有一个默认的 \(0\) 的前缀和, 这样我们有 \(n + 1\) 个前缀和,而任意两个前缀和相同就是一组解,根据鸽巢原理,一定有解

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 1000005;
inline int read(){
    int x = 0; char c = getchar();
    while(c < '0' || c > '9')c = getchar();
    do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c >= '0' && c <= '9');
    return x;
}
int n, a[maxn], s[maxn];
int las[maxn];
int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    int n = read();
    for(int i = 1; i <= n; ++i)a[i] = read() % n;
    for(int i = 1; i <= n; ++i)s[i] = (s[i - 1] + a[i]) % n;
    int pos = 0;
    for(int i = 1; i <= n; ++i)if(s[i] == 0){pos = i;break;}
    if(pos){
        printf("%d\n",pos);
        for(int i = 1; i <= pos; ++i)printf("%d ",i);
        return 0;
    }
    for(int i = 1; i <= n; ++i)if(las[s[i]]){pos = i; break;}else las[s[i]] = i;
    int l = las[s[pos]] + 1, r = pos;
    printf("%d\n",r - l + 1);
    for(int i = l; i <= r; ++i)printf("%d ",i);
    return 0;
}

B. Read

读错题,,,,,,垃圾题暴零, 我就是sb

给的书是无序的。。。。

那么就是找是否存在大于等于\((n + 1) / 2\)的书,直接摩尔投票

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxm = 1005;
inline int read(){
    int x = 0; char c = getchar();
    while(c < '0' || c > '9')c = getchar();
    do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c >= '0' && c <= '9');
    return x;
}
int m, k, cnt[maxm], x[maxm], y[maxm], z[maxm];

signed main(){
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);
    m = read(); k = read();
    int sn = 0;
    for(int i = 1; i <= m; ++i)cnt[i] = read();
    for(int i = 1; i <= m; ++i)sn += cnt[i];
    for(int i = 1; i <= m; ++i)x[i] = read();
    for(int i = 1; i <= m; ++i)y[i] = read();
    for(int i = 1; i <= m; ++i)z[i] = read();
    int s = (1 << k) - 1;
    int now, las = -1, ct = 0;
	for (int i = 1; i <= m; ++i) {
		now = x[i]; 
        if(ct && las != now)--ct;
        else las = now, ++ct;
		long long opt = x[i];
		for (int j = 1; j < cnt[i]; ++j) {
			opt = (opt * y[i] + z[i]) & s;
			now = opt; 
            if(ct && las != now)--ct;
            else las = now, ++ct;
		}
	}
    int sum = 0;
    for (int i = 1; i <= m; ++i) {
		now = x[i]; 
        if(now == las)++sum;
     	long long opt = x[i];
		for (int j = 1; j < cnt[i]; ++j) {
			opt = (opt * y[i] + z[i]) & s;
			now = opt; 
            if(now == las)++sum;
        }
	}
    printf("%d\n",max(0, sum - sn + sum - 1));

    return 0;
}

C. 题目交流通道

如果不考虑边权为 \(0\) 的,那么找出不经过 \(i – > j\) 的最短路径,判断与 \(i – > j\) 路径的大小关系简单维护答案

考场写出来,也发现会有算重的情况,但是并没有发现是因为边权为 \(0\)

现在考虑有边权为 \(0\) 的, 他们之间其实可以看做一个团, 答案对团内团外分别处理

对于团外,应该说是两个团之间, 我们用类似上面部分分的做法找出不经过 \(i – > j\) 的最短路径,注意这里是两个团,不是两个点,我们只能路过其他团,维护答案分情况讨论

如果该路径等于两团直接路径,那么这些路径可以在限制以上随便选 \((k – dis_{i, j} + 1) ^ {size_i \times size_j}\)

如果大于, 那么两团之间的路径只要不都是大于两团直接路径的即可, \((k – dis_{i, j} + 1) ^ {size_i \times size_j} – (k – dis_{i, j}) ^ {size_i \times size_j}\)

对于团内的我们用如下公式计算

设\(g_n\)表示 \(n\) 个点的图的方案数, \(f_n\) 表示 \(n\) 个点的团的方案数,

显然有\(g_n = (k + 1) ^ {(^n_2)}\)

那么\(f_n = g_n \sum_{i = 1} ^ {n – 1} f_i \times g_{n – i} \times (^{n – 1}_{i – 1}) \times k ^{i (n – i)}\)跟游乐园那个同理

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' || c > '9')c = getchar();
	do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c >= '0' && c <= '9');
	return x;
}
typedef long long  ll;
const int maxn = 405;
const int inf = 2147483647;
const int mod = 998244353;
int n, k;
int mp[maxn][maxn], f[maxn], g[maxn],c[maxn][maxn];
bool vis[maxn];
ll d[maxn][maxn];
int qpow(int x, int y){
	int ans = 1;
	for(; y; y >>= 1, x = 1ll * x * x % mod)if(y & 1)ans = 1ll * ans * x % mod;
	return ans;
}
struct SET{
	int size[maxn],f[maxn];
	void pre(){
		for(int i = 1; i <= n; ++i)size[i] = 1;
		for(int i = 1; i <= n; ++i)f[i] = i;
	}
	int fa(int x){return f[x] = f[x] == x ? x : fa(f[x]);}
	void hb(int x, int y){
		x = fa(x), y = fa(y);
		if(x != y){
			if(size[x] < size[y]){
				size[y] += size[x];
				f[x] = y;
			}else{
				size[x] += size[y];
				f[y] = x;
			}
		}
	}
}s;
int work(){
	for(int i = 1; i <= n; ++i)
	  for(int j = i + 1; j <= n; ++j)
		if(mp[i][j] != mp[j][i] || mp[i][j] > k)return 0;
	for(int i = 1; i <= n; ++i)if(mp[i][i])return 0;
	s.pre();
	for(int i = 1; i <= n; ++i)
	  for(int j = i + 1; j <= n; ++j)
	     if(mp[i][j] == 0)s.hb(i, j);
	for(int i = 1; i <= n; ++i)g[i] = qpow(k + 1, i * (i - 1) / 2);
	for(int i = 0; i <= n; ++i){
		c[i][0] = 1;
		for(int j = 1; j <= i; ++j)
		  c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
	}
	f[1] = 1;
	for(int i = 2; i <= n; ++i){
		f[i] = g[i];
		for(int j = 1; j <= i - 1; ++j){
			f[i] = (f[i] - 1ll * f[j] * g[i - j] % mod * c[i - 1][j - 1] % mod * qpow(k, j * (i - j)) % mod + mod) % mod;
		}
	}
	memset(d,0x3f,sizeof(d));
	for(int k = 1; k <= n; ++k){
		if(s.f[k] != k)continue;
	  	for(int i = 1; i <= n; ++i){
		  	if(s.f[i] != i || i == k)continue;
			for(int j = 1; j <= n; ++j){
			   if(s.f[j] != j || i == j || k == j)continue;
			   d[i][j] = min(d[i][j], (ll)mp[i][k] + mp[k][j]);
		  	}
	  	}
	}
	int ans = 1;
	for(int i = 1; i <= n; ++i){
		if(s.f[i] != i)continue;
		for(int j = i + 1; j <= n; ++j){
			if(s.f[j] != j || s.f[j] == s.f[i])continue;
			if(d[i][j] < mp[i][j])return 0;
			if(d[i][j] > mp[i][j])ans = 1ll * ans * (0ll + qpow(k - mp[i][j] +  1, s.size[i] * s.size[j]) - qpow(k - mp[i][j], s.size[i] * s.size[j])% mod) % mod;
			else ans = 1ll * ans * qpow(k - mp[i][j] +  1, s.size[i] * s.size[j]) % mod;
		}
	}
	for(int i = 1; i <= n; ++i)if(s.f[i] == i)ans = 1ll * ans * f[s.size[i]] % mod;
	return ans;
}
int main(){
	freopen("c.in", "r", stdin);
	freopen("c.out", "w",stdout);
	n = read(), k = read();
	for(int i = 1; i <= n; ++i)
	  for(int j = 1; j <= n; ++j)
		mp[i][j] = read();
	printf("%d\n",work());
	return 0;
}

D. 题目难度提升

从中位数往前找是否有相同的,有的话扔两个,再一个最大的一个较小的扔即可

没有的话,先把最小的扔进去,然后用对顶堆维护中位数

考虑加数的过程,要求中位数一直小于等于手中的最小值,

然后通过已经加入数的数量的奇偶判断一下是否需要放最小值,或者找最大的能放的

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
const int maxn = 100005;
inline int read(){
    int x = 0; char c = getchar();
    while(c < '0' || c > '9')c = getchar();
    do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c >= '0' && c <= '9');
    return x;
}
int a[maxn], ans[maxn];
int n;
bool check(){
    sort(a + 1,a + n + 1);
    int pos = (n + 1) / 2;
    while(pos > 1){
        if(a[pos] == a[pos - 1]){
			while(a[pos + 1] == a[pos]) ++pos;
            ans[1] = ans[2] = a[pos];
            int pl = pos - 2, pr = n, p = 2;
            while(pl > 0 && pr > pos){
                ans[++p] = a[pr]; --pr;
                ans[++p] = a[pl]; --pl;
            }
            while(pr > pos)ans[++p] = a[pr--];
			while(pl > 0)ans[++p] = a[pl--];
            return true;
        }
        --pos;
	}
	return false;
}
multiset<int>s;
priority_queue<int> qmax;
priority_queue<int, vector<int> , greater<int> > qmin;
void push(int x){
	if(qmax.empty() || x < qmax.top())qmax.push(x);
	else qmin.push(x);
	if(qmax.size() < qmin.size())qmax.push(qmin.top()), qmin.pop();
	if(qmax.size() > qmin.size() + 1)qmin.push(qmax.top()), qmax.pop();
}
void work(){
	ans[1] = a[1];
	for(int i = 2; i <= n; ++i)s.insert(a[i]);
	push(a[1]);
	int p = 1;
	while(!s.empty()){
		int mi = *s.begin(), now = 0;
		if(qmax.size() == qmin.size()){
			if(mi >= qmin.top())now = *--s.end();
			else now = mi;
		}else{
			if(!qmin.empty() && mi + mi >= qmax.top() + qmin.top())now = *--s.end();
			else now = *--s.upper_bound(mi + mi - qmax.top());
		}
		ans[++p] = now;
		push(now);
		s.erase(now);
	}
}
int main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    n = read();
    for(int i = 1; i <= n; ++i)a[i] = read();
	sort(a + 1, a + n + 1);
	if(check() == false)work();
    for(int i = 1; i <= n; ++i)printf("%d ",ans[i]);printf("\n");
    return 0;
}
————————

A. Set

还做过类似的题,但是真的忘了

发现该题特殊点在于有 \(n\) 个数,求能被 \(n\) 整除的,明明是两个看似无关的数据,却给了同一个值,那么这里就是解题的关键

我们维护前缀和,最多有 \(n\)种取值, 如果前缀和为 \(0\) 那么从一开始到这个位置就是一个合法解,所以我们有一个默认的 \(0\) 的前缀和, 这样我们有 \(n + 1\) 个前缀和,而任意两个前缀和相同就是一组解,根据鸽巢原理,一定有解

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 1000005;
inline int read(){
    int x = 0; char c = getchar();
    while(c < '0' || c > '9')c = getchar();
    do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c >= '0' && c <= '9');
    return x;
}
int n, a[maxn], s[maxn];
int las[maxn];
int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    int n = read();
    for(int i = 1; i <= n; ++i)a[i] = read() % n;
    for(int i = 1; i <= n; ++i)s[i] = (s[i - 1] + a[i]) % n;
    int pos = 0;
    for(int i = 1; i <= n; ++i)if(s[i] == 0){pos = i;break;}
    if(pos){
        printf("%d\n",pos);
        for(int i = 1; i <= pos; ++i)printf("%d ",i);
        return 0;
    }
    for(int i = 1; i <= n; ++i)if(las[s[i]]){pos = i; break;}else las[s[i]] = i;
    int l = las[s[pos]] + 1, r = pos;
    printf("%d\n",r - l + 1);
    for(int i = l; i <= r; ++i)printf("%d ",i);
    return 0;
}

B. Read

读错题,,,,,,垃圾题暴零, 我就是sb

给的书是无序的。。。。

那么就是找是否存在大于等于\((n + 1) / 2\)的书,直接摩尔投票

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxm = 1005;
inline int read(){
    int x = 0; char c = getchar();
    while(c < '0' || c > '9')c = getchar();
    do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c >= '0' && c <= '9');
    return x;
}
int m, k, cnt[maxm], x[maxm], y[maxm], z[maxm];

signed main(){
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);
    m = read(); k = read();
    int sn = 0;
    for(int i = 1; i <= m; ++i)cnt[i] = read();
    for(int i = 1; i <= m; ++i)sn += cnt[i];
    for(int i = 1; i <= m; ++i)x[i] = read();
    for(int i = 1; i <= m; ++i)y[i] = read();
    for(int i = 1; i <= m; ++i)z[i] = read();
    int s = (1 << k) - 1;
    int now, las = -1, ct = 0;
	for (int i = 1; i <= m; ++i) {
		now = x[i]; 
        if(ct && las != now)--ct;
        else las = now, ++ct;
		long long opt = x[i];
		for (int j = 1; j < cnt[i]; ++j) {
			opt = (opt * y[i] + z[i]) & s;
			now = opt; 
            if(ct && las != now)--ct;
            else las = now, ++ct;
		}
	}
    int sum = 0;
    for (int i = 1; i <= m; ++i) {
		now = x[i]; 
        if(now == las)++sum;
     	long long opt = x[i];
		for (int j = 1; j < cnt[i]; ++j) {
			opt = (opt * y[i] + z[i]) & s;
			now = opt; 
            if(now == las)++sum;
        }
	}
    printf("%d\n",max(0, sum - sn + sum - 1));

    return 0;
}

C. 题目交流通道

如果不考虑边权为 \(0\) 的,那么找出不经过 \(i – > j\) 的最短路径,判断与 \(i – > j\) 路径的大小关系简单维护答案

考场写出来,也发现会有算重的情况,但是并没有发现是因为边权为 \(0\)

现在考虑有边权为 \(0\) 的, 他们之间其实可以看做一个团, 答案对团内团外分别处理

对于团外,应该说是两个团之间, 我们用类似上面部分分的做法找出不经过 \(i – > j\) 的最短路径,注意这里是两个团,不是两个点,我们只能路过其他团,维护答案分情况讨论

如果该路径等于两团直接路径,那么这些路径可以在限制以上随便选 \((k – dis_{i, j} + 1) ^ {size_i \times size_j}\)

如果大于, 那么两团之间的路径只要不都是大于两团直接路径的即可, \((k – dis_{i, j} + 1) ^ {size_i \times size_j} – (k – dis_{i, j}) ^ {size_i \times size_j}\)

对于团内的我们用如下公式计算

设\(g_n\)表示 \(n\) 个点的图的方案数, \(f_n\) 表示 \(n\) 个点的团的方案数,

显然有\(g_n = (k + 1) ^ {(^n_2)}\)

那么\(f_n = g_n \sum_{i = 1} ^ {n – 1} f_i \times g_{n – i} \times (^{n – 1}_{i – 1}) \times k ^{i (n – i)}\)跟游乐园那个同理

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
	int x = 0; char c = getchar();
	while(c < '0' || c > '9')c = getchar();
	do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c >= '0' && c <= '9');
	return x;
}
typedef long long  ll;
const int maxn = 405;
const int inf = 2147483647;
const int mod = 998244353;
int n, k;
int mp[maxn][maxn], f[maxn], g[maxn],c[maxn][maxn];
bool vis[maxn];
ll d[maxn][maxn];
int qpow(int x, int y){
	int ans = 1;
	for(; y; y >>= 1, x = 1ll * x * x % mod)if(y & 1)ans = 1ll * ans * x % mod;
	return ans;
}
struct SET{
	int size[maxn],f[maxn];
	void pre(){
		for(int i = 1; i <= n; ++i)size[i] = 1;
		for(int i = 1; i <= n; ++i)f[i] = i;
	}
	int fa(int x){return f[x] = f[x] == x ? x : fa(f[x]);}
	void hb(int x, int y){
		x = fa(x), y = fa(y);
		if(x != y){
			if(size[x] < size[y]){
				size[y] += size[x];
				f[x] = y;
			}else{
				size[x] += size[y];
				f[y] = x;
			}
		}
	}
}s;
int work(){
	for(int i = 1; i <= n; ++i)
	  for(int j = i + 1; j <= n; ++j)
		if(mp[i][j] != mp[j][i] || mp[i][j] > k)return 0;
	for(int i = 1; i <= n; ++i)if(mp[i][i])return 0;
	s.pre();
	for(int i = 1; i <= n; ++i)
	  for(int j = i + 1; j <= n; ++j)
	     if(mp[i][j] == 0)s.hb(i, j);
	for(int i = 1; i <= n; ++i)g[i] = qpow(k + 1, i * (i - 1) / 2);
	for(int i = 0; i <= n; ++i){
		c[i][0] = 1;
		for(int j = 1; j <= i; ++j)
		  c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
	}
	f[1] = 1;
	for(int i = 2; i <= n; ++i){
		f[i] = g[i];
		for(int j = 1; j <= i - 1; ++j){
			f[i] = (f[i] - 1ll * f[j] * g[i - j] % mod * c[i - 1][j - 1] % mod * qpow(k, j * (i - j)) % mod + mod) % mod;
		}
	}
	memset(d,0x3f,sizeof(d));
	for(int k = 1; k <= n; ++k){
		if(s.f[k] != k)continue;
	  	for(int i = 1; i <= n; ++i){
		  	if(s.f[i] != i || i == k)continue;
			for(int j = 1; j <= n; ++j){
			   if(s.f[j] != j || i == j || k == j)continue;
			   d[i][j] = min(d[i][j], (ll)mp[i][k] + mp[k][j]);
		  	}
	  	}
	}
	int ans = 1;
	for(int i = 1; i <= n; ++i){
		if(s.f[i] != i)continue;
		for(int j = i + 1; j <= n; ++j){
			if(s.f[j] != j || s.f[j] == s.f[i])continue;
			if(d[i][j] < mp[i][j])return 0;
			if(d[i][j] > mp[i][j])ans = 1ll * ans * (0ll + qpow(k - mp[i][j] +  1, s.size[i] * s.size[j]) - qpow(k - mp[i][j], s.size[i] * s.size[j])% mod) % mod;
			else ans = 1ll * ans * qpow(k - mp[i][j] +  1, s.size[i] * s.size[j]) % mod;
		}
	}
	for(int i = 1; i <= n; ++i)if(s.f[i] == i)ans = 1ll * ans * f[s.size[i]] % mod;
	return ans;
}
int main(){
	freopen("c.in", "r", stdin);
	freopen("c.out", "w",stdout);
	n = read(), k = read();
	for(int i = 1; i <= n; ++i)
	  for(int j = 1; j <= n; ++j)
		mp[i][j] = read();
	printf("%d\n",work());
	return 0;
}

D. 题目难度提升

从中位数往前找是否有相同的,有的话扔两个,再一个最大的一个较小的扔即可

没有的话,先把最小的扔进去,然后用对顶堆维护中位数

考虑加数的过程,要求中位数一直小于等于手中的最小值,

然后通过已经加入数的数量的奇偶判断一下是否需要放最小值,或者找最大的能放的

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
const int maxn = 100005;
inline int read(){
    int x = 0; char c = getchar();
    while(c < '0' || c > '9')c = getchar();
    do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c >= '0' && c <= '9');
    return x;
}
int a[maxn], ans[maxn];
int n;
bool check(){
    sort(a + 1,a + n + 1);
    int pos = (n + 1) / 2;
    while(pos > 1){
        if(a[pos] == a[pos - 1]){
			while(a[pos + 1] == a[pos]) ++pos;
            ans[1] = ans[2] = a[pos];
            int pl = pos - 2, pr = n, p = 2;
            while(pl > 0 && pr > pos){
                ans[++p] = a[pr]; --pr;
                ans[++p] = a[pl]; --pl;
            }
            while(pr > pos)ans[++p] = a[pr--];
			while(pl > 0)ans[++p] = a[pl--];
            return true;
        }
        --pos;
	}
	return false;
}
multiset<int>s;
priority_queue<int> qmax;
priority_queue<int, vector<int> , greater<int> > qmin;
void push(int x){
	if(qmax.empty() || x < qmax.top())qmax.push(x);
	else qmin.push(x);
	if(qmax.size() < qmin.size())qmax.push(qmin.top()), qmin.pop();
	if(qmax.size() > qmin.size() + 1)qmin.push(qmax.top()), qmax.pop();
}
void work(){
	ans[1] = a[1];
	for(int i = 2; i <= n; ++i)s.insert(a[i]);
	push(a[1]);
	int p = 1;
	while(!s.empty()){
		int mi = *s.begin(), now = 0;
		if(qmax.size() == qmin.size()){
			if(mi >= qmin.top())now = *--s.end();
			else now = mi;
		}else{
			if(!qmin.empty() && mi + mi >= qmax.top() + qmin.top())now = *--s.end();
			else now = *--s.upper_bound(mi + mi - qmax.top());
		}
		ans[++p] = now;
		push(now);
		s.erase(now);
	}
}
int main(){
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    n = read();
    for(int i = 1; i <= n; ++i)a[i] = read();
	sort(a + 1, a + n + 1);
	if(check() == false)work();
    for(int i = 1; i <= n; ++i)printf("%d ",ans[i]);printf("\n");
    return 0;
}