CSUST2021省赛选拔赛题解
前言
对不起实在是太困了暑训一结束就去整补考了，代码都没咋敲，直接回到解放前。
A
题意
n堆棋子（n为偶数），两人轮流取，每次取\frac{n}{2}堆，每堆可以取任意正整数个，谁先取不了为输，问谁输谁赢。(sora shiro天下第一)
题解
也算是比较常见套路的博弈题随便猜了一发被x了心态就不好了
首先考虑必输态，如果当前存在小于等于\frac{n}{2}个为0的堆，那么下一个人必输，因为当前人可以把不为0的\frac{n}{2}堆拿光。
那么先手操作的时候可以选\frac{n}{2}堆，把他们都变成当前最小数，那么后手必定会操作到一个当前最小数，但是又不能拿光否则就输了。然后先手不断重复这个过程直到把后手逼输即可。前提是一开始最小的数就大于等于一半。
代码
#include<iostream>
using namespace std;
int a[200];
int main()
{
int n,m=200;
cin>>n;
int sum=0;
for(int i=1;i<=n;i++)cin>>a[i],m=min(m,a[i]);
for(int i=1;i<=n;i++)if(a[i]==m)sum++;
if(sum<=n/2)cout<<"Bai\n";
else cout<<"Kong\n";
return 0;
}
B
题意
求能被m整除的最小n位自然数。
题解
签到，一开始想的二分（其实二分也能做吧），后来想想其实直接对10^n取模，然后再补齐即可。需要特别注意的是，0整除所有自然数。
代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
using ll=long long;
const int maxn=1e5+10;
const int mod=1e9+7;
const double eps=1e-7;
vector<int>res;
ll mi[20];
int main()
{
mi[1]=1;
for(int i=2;i<=19;i++)mi[i]=mi[i-1]*10;
int t;
cin>>t;
while(t--)
{
ll n,m;
cin>>n>>m;
if(n==1)cout<<0<<endl;
else if(mi[n]<m/10+1)cout<<-1<<endl;
else cout<<mi[n]+((mi[n]%m==0)?0ll:(m-mi[n]%m))<<endl;
}
return 0;
}
C
数据好像还没修好，所以没补。（别修了，累了）
D
题意
n个机器，工作时间为T。对第i个机器可以花y_i时间修理，从而获得x_i*res的金钱。（x_i表示第i个机器的性能，res表示修理完当前机器后剩余的时间），求最大收益。
题解
对每台机器性能与花费的比值\frac{x_i}{y_i}排序，然后就转化为01背包问题。排序是为了在更早的时间选性价比更高的机器，之所以这样贪是由res决定的，越早价值越高。
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
using ll=long long;
using PII=pair<int,int>;
const int maxn=1e5+10;
PII a[maxn];
ll dp[600];
int main()
{
ios::sync_with_stdio(false);
int n,t;
cin>>n>>t;
for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;
sort(a+1,a+1+n,[](PII a,PII b){return a.first*b.second>b.first*a.second;});
ll ans=0;
for(int i=1;i<=n;i++)
for(int j=t;j>=a[i].second;j--)
dp[j]=max(dp[j],dp[j-a[i].second]+a[i].first*(t-j)),ans=max(ans,dp[j]);
cout<<ans<<endl;
return 0;
}
E
题意
求n*m的网格中一共有几个正方形。
题解
正推其实还蛮难推，打表可以看出规律。
推导
- 对于n*n的点阵排斥边界，所含有的正方形（正的和斜的）个数为n-1
- 在$nm的点阵中，所含有的kk的排斥边界的个数为(n-k+1)(m-k+1)$
由此可得公式
ans=\sum\limits^{\min(n,m)}_{i=2}(n-i+1)(m-i+1)(i-1)=\sum\limits^{\min(n,m)-1}_{i-1=1}(n-(i-1))(m-(i-1))(i-1)
化简得
ans=\sum\limits^{\min(n,m)}_{i=1}(n-i)(m-i)i
运用等幂求和公式可以优化到O(1)。
代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
using ll=long long;
const int maxn=1e6+10;
const int mod=1e9+7;
const double eps=1e-7;
ll power(ll a,ll b)
{
ll res=1;
while(b>0)
{
if(b&1)res=(res*a)%mod;
b>>=1;
a=(a*a)%mod;
}
return res;
}
int main()
{
ll n,m;
cin>>n>>m;
if(m<n)swap(n,m);
ll ans=0;
for(int i=1;i<=n;i++){
ans=(ans%mod+((n-i+1)%mod*(m-i+1)%mod*i%mod)%mod)%mod;
}
cout<<ans<<endl;
return 0;
}
F
题意
n*m个数组成数阵，给出一个长度为s的数列，要求在数阵中选出连续一排长度为s个数，使得他们的和一致并且都不超过9，问有多少方案。
题解
对每一位进行枚举，因为一共只有9种可能。然后用KMP匹配字符串即可。
代码
#include <iostream>
using namespace std;
const int maxn = 1e6 + 10;
string a[maxn];
string h;
int ne[maxn];
int main()
{
int t;
cin >> t;
while (t--) {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= n; i++)
cin >> a[i];
cin >> h;
int ans = 0;
for (char c = '9'; c >= '0'; c--) {
for (int k = 1; k <= n; k++) {
string p;
for (int i = 0; i < h.length(); i++) {
p += c - h[i] + '0';
}
for (int i = 1, j = 0; i < p.length(); i++) {
while (j && p[i] != p[j])
j = ne[j - 1];
if (p[i] == p[j])
j++;
ne[i] = j;
}
for (int i = 0, j = 0; i < a[k].length(); i++) {
while (j && a[k][i] != p[j])
j = ne[j - 1];
if (a[k][i] == p[j])
j++;
if (j == p.length())
ans++;
}
}
}
cout << ans << endl;
}
return 0;
}
G
题意
N个数严格递增，K次操作，每次对一个区间加上一个数，每次操作后判断N个数中是否存在A_i=i。
题解
原数组严格递增，对其中一个区间加上一个数后可能会破坏单调性，最多把原区间分成三份。思路是模拟，用类似线段树的节点去存每个区间的增加值，每次更新同时更新这个区间和前后两个区间的情况，按照边界分类讨论。如此一来，对于每个节点的区间内部都是单调的，二分搜索是否存在满足条件的数即可。
因为懒得讨论了，所以这里贴了lkw学长的代码。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 5, inf = 0x3f3f3f3f, mod = 1e9 + 7;
//我看不懂但我大为震撼
int n, k;
int a[maxn];
//原数组严格递增，对其中一个区间加上一个数后可能会破坏原来整个数组的严格递增性
//分情况讨论，每次操作最多把数组拆成3个部分
struct node { //存每个区间的加数情况
int l, r;
int add;
};
vector<node> temp; //存多出来的区间
vector<node> vec; //存整个数组所有的加数情况
//保证每个区间的非严格递增性
//然后对每个区间二分去找是否有满足条件的
signed main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i] = a[i] - i;//a[i]=0时就成立
}
vec.push_back({ 1, n, 0 });
for (int i = 1, l, r, c; i <= k; i++) {
scanf("%d%d%d", &l, &r, &c);
for (int j = 0; j < vec.size(); j++) {
node now = vec[j];
node x, y, z;
x = now;
if (x.l > x.r)
continue;
if (l <= x.l && x.r <= r) {
x.add += c;
} else if (x.l <= l && r <= x.r) {
x.r = l - 1;
y.add = x.add + c;
y.l = l;
y.r = r;
z.l = r + 1;
z.r = now.r;
z.add = now.add;
if (z.r >= z.l) {
temp.push_back(z);
}
if (y.r >= y.l) {
temp.push_back(y);
}
} else if (x.r >= l && x.l < l) {
x.r = l - 1;
y.add = x.add + c;
y.l = l;
y.r = now.r;
if (y.r >= y.l) {
temp.push_back(y);
}
} else if (x.r > r && x.l <= r) {
x.r = r;
x.add += c;
y.l = r + 1;
y.r = now.r;
y.add = now.add;
if (y.r >= y.l) {
temp.push_back(y);
}
}
vec[j] = x;
}
for (auto x : temp) {
vec.push_back(x);
}
temp.clear();
bool flag = 0;
for (auto x : vec) {
if (x.l > x.r)
continue;
int cha = -x.add;
if (a[x.r] < cha || a[x.l] > cha)
continue;
int big = *lower_bound(a + 1 + x.l - 1, a + 1 + x.r, cha);
if (big == cha) {
flag = 1;
break;
}
}
printf(flag ? "YES\n" : "NO\n");
}
return 0;
}
H
题意
定义F(x)为x的数位和，求所有满足F(x)+x=n的x。
题解
签到，可以发现F(x)的范围很小，那么x=n-F(x)，枚举x即可。
代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
using ll=long long;
const int maxn=1e5+10;
const int mod=1e9+7;
const double eps=1e-7;
vector<ll>res;
ll n;
bool check(ll u)
{
ll t=u,sum=0;
while(t)
{
sum+=t%10;
t/=10;
}
return (u+sum)==n;
}
int main()
{
cin>>n;
ll t=n;
ll ans=0;
int len=0;
while(t)len++,t/=10;
ll l=n-9*len;
for(;l<n;l++){
if(check(l)){
res.push_back(l);
ans++;
}
}
cout<<ans<<endl;
for(auto i:res)cout<<i<<endl;
return 0;
}
I
题意
给两个数字串s和t，每次可以选择s中一个非空子串按数字升序排列，问能否通过有限次操作将s变为t。
题解
为缩小思考复杂度，考虑每次只交换两个数。对于t来说，每个数字所在的位置都是确定的，那么我们只要对s中每个数字进行判断它能否移动到需要的位置。判断的条件是在移动的过程中是否存在比它小的数字即可。（因为比它小的数字会塞住它交换的路）
代码
#include <iostream>
using namespace std;
const int maxn = 1e5 + 10;
int cnt[15], pos[15][maxn];
string s, t;
int main()
{
cin >> s >> t;
for (int i = s.length() - 1; i >= 0; i--) {
int d = s[i] - '0';
pos[d][++cnt[d]] = i;//记录每一个数的位置
}
bool ans = true;
for (auto c : t) {
int d = c - '0';
if (cnt[d] == 0) {
ans = false;
break;
}
bool flag = true;
for (int i = 0; i < d; i++) {
if (cnt[i] && pos[i][cnt[i]] < pos[d][cnt[d]]) { //比d小的数在d之前
flag = false;
break;
}
}
if (!flag) {
ans = false;
break;
}
cnt[d]--;
}
return cout << (ans ? "True" : "False"), 0;
}
J
题意
给出n个数，有两种操作。
- 对区间每个数增加v
- 查询\sum\limits_{i=l}^r\sum\limits_{j=i+1}^ra_i*a_j。
题解
显然是数据结构题，然后显然线段树可以解决。问题是如何计算一个区间中两两数之间的乘积。
正推困难，先考虑增加v对公式的影响。发现每一项都会出一个v^2和$va，vb$。全部加起来就可以得到区间价值等于左右儿子的价值和加上左右儿子的区间和之积。
代码
#include <iostream>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
//先考虑懒标记对价值的影响
//得到公式，每一项会出一个v^2，va，vb
//得到两个区间合并的关系
int a[maxn];
struct Node {
int l, r;
ll sum, res, add;
} tr[maxn << 2];
void pushup(int node)
{
tr[node].sum = (tr[node << 1].sum + tr[node << 1 | 1].sum) % mod;
tr[node].res = ((tr[node << 1].res + tr[node << 1 | 1].res) % mod + tr[node << 1].sum * tr[node << 1 | 1].sum % mod) % mod;
}
void pushdown(int node)
{
if (tr[node].add) {
ll& v = tr[node].add;
tr[node << 1].add = (tr[node << 1].add + v) % mod;
tr[node << 1 | 1].add = (tr[node << 1 | 1].add + v) % mod;
int l = tr[node << 1].r - tr[node << 1].l + 1;
int r = tr[node << 1 | 1].r - tr[node << 1 | 1].l + 1;
tr[node << 1].res = (tr[node << 1].res + (l - 1) * tr[node << 1].sum % mod * v + (l - 1) * l / 2 % mod * v % mod * v % mod) % mod;
tr[node << 1 | 1].res = (tr[node << 1 | 1].res + (r - 1) * tr[node << 1 | 1].sum % mod * v + (r - 1) * r / 2 % mod * v % mod * v % mod) % mod;
tr[node << 1].sum = (tr[node << 1].sum + l * v % mod) % mod;
tr[node << 1 | 1].sum = (tr[node << 1 | 1].sum + r * v % mod) % mod;
v = 0;
}
}
void build(int node, int l, int r)
{
tr[node] = { l, r };
tr[node].add = 0;
if (l == r) {
tr[node].sum = a[l];
tr[node].res = 0;
return;
}
int mid = l + r >> 1;
build(node << 1, l, mid), build(node << 1 | 1, mid + 1, r);
pushup(node);
}
PII query(int node, int l, int r)
{
if (tr[node].l >= l && tr[node].r <= r) {
PII a;
a.first = tr[node].sum, a.second = tr[node].res;
return a;
}
pushdown(node);
int mid = tr[node].l + tr[node].r >> 1;
PII a, b, c;
int x = 0, y = 0;
if (l <= mid)
a = query(node << 1, l, r), x = 1;
if (r > mid)
b = query(node << 1 | 1, l, r), y = 1;
if (x + y == 2) {
c.first = (a.first + b.first) % mod;
c.second = ((a.second + b.second) % mod + (a.first * b.first % mod)) % mod;
return c;
}
return x ? a : b;
}
void update(int node, int l, int r, ll v)
{
if (tr[node].l >= l && tr[node].r <= r) {
tr[node].add += v;
int len = tr[node].r - tr[node].l + 1;
tr[node].res = (tr[node].res + (len - 1) * tr[node].sum % mod * v + (len - 1) * len / 2 % mod * v % mod * v % mod) % mod;
tr[node].sum = (tr[node].sum + len * v % mod) % mod;
return;
}
pushdown(node);
int mid = tr[node].l + tr[node].r >> 1;
if (l <= mid)
update(node << 1, l, r, v);
if (r > mid)
update(node << 1 | 1, l, r, v);
pushup(node);
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
while (m--) {
int op, l, r, v;
cin >> op >> l >> r;
if (op == 1) {
cin >> v;
update(1, l, r, v);
} else {
cout << query(1, l, r).second << endl;
}
}
}
return 0;
}
总结
题目使用的算法依然没有什么新学的东西，主要还是考了思维和代码能力。总而言之还是写的太少了呜呜呜
Comments | NOTHING