2023CCPC秦皇岛比赛部分题解
A.贵校是构造王国吗I
众所周知，你们正在参加中国构造题竞赛（Chinese Constructive Problem Contest, CCPC），毫无疑问，命题学校中山大学身为构造王国非常希望你们去挑战一些相关的问题。
给定一个 \(n \times n\) 的网格，你需要将 \([1,k]\) 内的填入网格中，并且满足以下要求。
数字 \(1\) 到 \(k\) 恰好出现一次。
每个单元格最多填入一个数字。
每行和每列应至少有两个数字。
对于每个整数 \(i\in [1,n]\)，第 \(i\) 行所有数字的最大公约数应等于第 \(i\) 列所有数字的最大公约数。
保证在输入的限制下一定存在一个合法的方案。
$Input$输入只有一行，包含两个整数 \(n\) 和 \(k\ (\ 2\leq n\leq 2\times 10^5,\ 2\times n \leq k\leq min(n^2,10^6)\ )\) — 表示矩阵的大小和需要填入的数字数量。
$Output$你应该输出 \(k\) 行，第 \(i\) 行由两个整数 \(x_i\) 和 \(y_i\) 组成，表示数字 \(i\) 填入位置所对应的行号和列号。
如果有多种方案，输出任意一个即可。
\(Sample\)
3 6
——————
1 1
2 2
1 3
2 3
3 1
3 2
思路：想让横和行\(gcd\)相同，首先倾向于构造成1是最好的，随后动手画画，如果阶梯型构造放连续的数显然是可以的，最后在\((n,1)\)再放一个数，
有多的数在其他空位置随便放就可以了，时间复杂度不会太大
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll long long
#define lowbit(x) (x & -x)
#define endl "\n"
using namespace std;
mt19937 rnd(time(0));
const ll mod=1e9+7;
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
{
ans=ans%mod*(x%mod)%mod;
}
x=x%mod*(x%mod)%mod;
y>>=1;
}
return ans;
}
ll gcd(ll x, ll y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fio();
ll n,k;
cin>>n>>k;
map<pair<ll,ll>,bool>q;
for(ll i=1;i<=n;i++)
{
for(ll j=i;j<=min(i+1,n);j++)
{
k--;
cout<<i<<" "<<j<<endl;
q[{i,j}]=1;
}
}
cout<<n<<" "<<1<<endl;
k--;
q[{n,1}]=1;
for(ll i=1;i<=n;i++)
{
if(k==0)
{
break;
}
for(ll j=1;j<=n;j++)
{
if(q[{i,j}])continue;
cout<<i<<" "<<j<<endl;
k--;
if(k==0)
break;
}
}
}
D.茶和咖啡
中山大学的女孩们喜欢喝茶。但是有一天，她们想要变换口味，所以决定在接下来的 \(n\) 天里尝试一下喝咖啡。
现在，总是为中山大学提供食物和饮料的 Zayin 决定去商店买一些咖啡，她了解到第 \(i\) 天的价格是 \(a_i\)。同时，她有 \(m\) 张优惠券 — 第 \(i\) 张优惠券可以在前 \(r_i\) 天（包括第 \(r_i\) 天）使用，并且可以将当天咖啡的价格减少 \(w_i\)。
请注意，每张优惠券只能使用一次，Zayin 可以在一天内使用多张优惠券。使用优惠券后，价格可以是负数。
由于中山大学的女孩们仍然需要喝茶，Zayin 决定选择只在某些天内购买咖啡。现在她想知道，如果她选择恰好 \(k\ (1\le k \le n)\) 天来购买咖啡，她需要花费的最少金额（或者她可以获得的最大金额）是多少呢？
\(Input\)
输入的第一行包含一个整数 \(t\ (1\le t\le 10)\) — 表示测试用例的数量。接下来是测试用例的描述。
第一行包含两个整数 \(n,m\ (1\le n, m\le 2\times 10^5)\) — 表示天数和优惠券的数量。
第二行包含 \(n\) 个整数 \(a_1,a_2,\cdots,a_n\ (1\le a_i \le 10^9)\) — 其中 \(a_i\) 表示第 \(i\) 天咖啡的价格。
接下来的 \(m\) 行，每行包含两个整数 \(r_i,w_i\ (1\le r_i\le n,\ 1\le w_i\le 10^9)\) — 表示第 \(i\) 张优惠券可以在前 \(r_i\) 使用，并且可以将价格减少 \(w_i\)。
\(Output\)
对于每个测试用例，输出 \(n\) 个整数 — 第 \(i\) 个整数表示 Zayin 恰好选择 \(i\) 天购买咖啡时所花费的最少金额。
\(Sample\)
2
5 2
1 2 3 4 5
3 1
4 2
7 3
4 3 1 10 3 8 6
4 9
3 8
4 5
————————————
-2 0 3 7 12
-21 -18 -15 -11 -5 3 13
思路：题意是选取最小费用的\(i\)个咖啡，统计最小费用。
思考如何使用优惠卷？对于一个优惠卷使用期之内，肯定选取优惠期内费用最小的咖啡进行优惠（只考虑现在快到期的优惠卷），因为使用期外就没法用了。如果在这个优惠卷到期和下个优惠卷使用期之内有更小费用的咖啡现在应该更换下个优惠卷使用的目标，但是上个优惠卷还是继续使用
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll long long
#define lowbit(x) (x & -x)
#define endl "\n"
using namespace std;
mt19937 rnd(time(0));
const ll mod=1e9+7;
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
{
ans=ans%mod*(x%mod)%mod;
}
x=x%mod*(x%mod)%mod;
y>>=1;
}
return ans;
}
ll gcd(ll x, ll y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll a[250000];
struct s
{
ll t,w;
}p[500000];
ll pre[250000];
bool cmp(s x,s y)
{
return x.t<y.t;
}
int main()
{
fio();
ll t;
cin>>t;
while(t--)
{
ll n,m;
cin>>n>>m;
ll sum=0;
for(ll i=1;i<=n;i++)cin>>a[i];
for(ll i=1;i<=m;i++)cin>>p[i].t>>p[i].w,sum+=p[i].w;
sort(p+1,p+1+m,cmp);
p[m+1].t=9999999999;
ll wz=1;
ll ans=9999999999;
ll u=0;
for(ll i=1;i<=n;i++)
{
if(i<p[wz].t)
{
if(ans>a[i])
{
ans=a[i];
u=i;
}
}
else if(i==p[wz].t)
{
if(ans>a[i])
{
ans=a[i];
u=i;
}
while(p[wz].t==i)
{
a[u]-=p[wz].w;
wz++;
}
ans=a[u];
}
}
//ll ans=0;
ans=0;
sort(a+1,a+1+n);
for(ll i=1;i<=n;i++)
{
ans+=a[i];
cout<<ans<<" ";
}
cout<<endl;
}
}
F.质数之谜
数学王国的质数部长是质数的狂热追随者，因此他特别设立了一个部门来解决与质数相关的问题。这个部门的负责人罗伯特先生最近收到了他的朋友欧拉的一封信。
这封信中包含了一个关于质数的谜题。欧拉认为序列 \(a_1, a_2, ..., a_n\) 是美丽的当且仅当所有元素都是正整数，并且任意两个相邻元素的和是一个质数。
形式化地说，\(\forall i\in [1, n] \cap \mathbb{N}, a_i \in \mathbb{N}^+,\forall i\in [1, n) \cap \mathbb{N}, (a_i+a_{i+1}) \in \mathbb{P}\)，其中 \(\mathbb{P}\) 表示包含所有质数的集合。
有时，欧拉信中给定的序列并不美丽。罗伯特先生希望通过修改最少数量的序列元素使其变得美丽。
罗伯特先生最近很忙，所以他想请你帮忙计算使序列变得美丽的最小修改数量。
$Input$第一行包含一个整数 \(n\ (2\le n \le 10^5)\)。
第二行包含 \(n\) 个正整数，表示 \(a_1, a_2,...,a_n\ (1\le a_i\le 10^5)\)。
$Output$输出一个整数，表示使序列变得美丽的最小更新元素数量。
\(Sample1\)
6
1 5 1 4 4 1
——————————
2
\(Sample2\)
9
30 6 7 12 15 8 20 17 14
——————————————
4
思路：可以去了解下这个波利尼亚克猜想，在题目给出的范围内，想要构成一组连续的质数，除了（1，1），其他必须得按照奇偶交换排序
所以可以\(dp\)了，设\(0,1,2,3\)分别为变1，变偶，变比1大的奇数，不变，开个\(dp[325000][4]\)就可以直接线性\(dp\)得解了。
注意：得区分好变的情况，他不是固定的，他只是一个任意满足条件的数而已，但是对于固定的得细细讨论
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll long long
#define lowbit(x) (x & -x)
#define endl "\n"
using namespace std;
mt19937 rnd(time(0));
const ll mod=1e9+7;
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
{
ans=ans%mod*(x%mod)%mod;
}
x=x%mod*(x%mod)%mod;
y>>=1;
}
return ans%mod%mod;
}
ll gcd(ll x, ll y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
bool st[500000];
ll zs[4500000];
ll cn=0;
void ola(ll x)
{
for(ll i=2;i<=x;i++)
{
if(!st[i])cn++,zs[cn]=i;
for(ll j=1;zs[j]<=x/i;j++)
{
st[i*zs[j]]=1;
if(i%zs[j]==0)break;
}
}
}
ll a[325000];
ll dp[325000][4];//变1,变偶,不为1的奇,不变.0 1 2 3
map<ll,ll>mp;
int main()
{
fio();
ola(200005);
ll n;
cin>>n;
for(ll i=1;i<=cn;i++)
{
mp[zs[i]]=1;
}
for(ll i=1;i<=n;i++)cin>>a[i];
for(ll i=1;i<=n;i++)
{
dp[i][0]=dp[i][1]=dp[i][2]=i;//最坏情况赋值
dp[i][3]=i-1;
if(i>=2)
{
if(mp[a[i-1]+a[i]])dp[i][3]=min(dp[i-1][3],dp[i][3]);
if(mp[1+a[i]])dp[i][3]=min(dp[i][3],dp[i-1][0]);
if(mp[a[i-1]+1])dp[i][0]=min(dp[i][0],dp[i-1][3]+1);
dp[i][0]=min({dp[i][0],dp[i-1][0]+1,dp[i-1][1]+1});
dp[i][1]=min({dp[i][1],dp[i-1][0]+1,dp[i-1][2]+1});
dp[i][2]=min({dp[i][2],dp[i-1][1]+1});
if(a[i-1]==1)dp[i][0]=min(dp[i][0],dp[i-1][3]+1),dp[i][1]=min(dp[i][1],dp[i-1][3]+1);
else if(a[i-1]%2==0)dp[i][2]=min(dp[i][2],dp[i-1][3]+1);
else dp[i][1]=min(dp[i][1],dp[i-1][3]+1);
if(a[i]==1)dp[i][3]=min({dp[i][3],dp[i-1][0],dp[i-1][1]});
else if(a[i]%2==0)dp[i][3]=min(dp[i][3],dp[i-1][2]);
else dp[i][3]=min(dp[i][3],dp[i-1][1]);
}
}
cout<<min({dp[n][0],dp[n][1],dp[n][2],dp[n][3]})<<endl;
}
G.最大路径
给定长度为 \(n\) 的数组 \(a\) 和长度为 \(m\) 的数组 \(b\)，定义一个大小为 \(n \times m\) 的网格，其中单元格 \((x,y)\) 的值表示为 \(C[x,y]=a_x + b_y\)。
你要从 \((1,1)\) 开始，每一步可以选择移动到位于当前位置右下的某个网格，直到到达\((n,m)\)，目标是最大化路径上相邻单元格之间绝对差值的和。
具体而言，你的目标是找到一个满足以下条件的序列 \((x_1,y_1), (x_2,y_2), ..., (x_k,y_k)\)：
- \((x_1,y_1) = (1,1)\)
- \((x_k,y_k) = (n,m)\)
- \(x_i \le x_{i+1},\ y_i \le y_{i+1},\ (x_i,y_i) \neq (x_{i+1},y_{i+1})\ \forall i\in [1, k)\)
同时最大化 \(\sum_{i=1}^{k-1} {|C[x_i,y_i]-C[x_{i+1},y_{i+1}]|}\)。
$Input$第一行包含两个整数 \(n, m\ (1\le n,m \le 10^5)\)。
第二行包含 \(n\) 个整数，表示数组 \(a\ (1\le a_i\le 10^5)\)。
第三行包含 \(m\) 个整数，表示数组 \(b\ (1\le b_i\le 10^5)\)。
$Output$输出一行包含一个整数，表示答案。
\(Sample1\)
4 4
1 3 3 1
8 10 8 5
————————
11
\(Sample2\)
4 2
5 7 8 10
10 3
————————
12
思路：题目得认真看，就是会有个\(n*m\)矩阵，矩阵\((x,y)\)位置代表\(a_x+b_y\)，你得从\((1，1)\)跳到\((n,m)\)，每次只能选择跳到右下角位置
对于\(1->5\)，如果中间跳到\(3\)再跳到\(5\)，值为\(|5-1|\)，如果是跳到\(6\)再跳到\(5\)，值为|6-1|+|6-5|值会更大
所以对于这个网格得移动法，就得一个一个移动（下移或者右移），然后发现同一行或者同一列，两个连续的数相减，会变成单个数组内相邻数字的相减,\((1,1)->(1,2)\)等于\(b_1-b_2\)
所以直接取数组\((\sum_{i=2}^{n} |(a[i]-a[i-1])|)+\sum_{i=2}^{n} |b[i]-b[i-1]|)\)即可
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll long long
#define lowbit(x) (x & -x)
#define endl "\n"
using namespace std;
mt19937 rnd(time(0));
const ll mod=1e9+7;
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
{
ans=ans%mod*(x%mod)%mod;
}
x=x%mod*(x%mod)%mod;
y>>=1;
}
return ans;
}
ll gcd(ll x, ll y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll a[325000];
ll b[325000];
int main()
{
fio();
ll n,m;
cin>>n>>m;
ll ans=0;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
if(i>=2)
ans+=abs(a[i]-a[i-1]);
}
for(ll j=1;j<=m;j++)
{
cin>>b[j];
if(j>=2)
ans+=abs(b[j]-b[j-1]);
}
cout<<ans<<endl;
}
J.维克多词典
Keyi 是一个热爱读书的中学生，并养成了每天早上阅读的习惯。
随着高考的临近，Keyi 计划每天从《维克多词典》中学习几个单词。
然而，她记忆单词的方法有点奇特。如果她今天学习了一个长度为 \(k\) 的单词，她坚持要在当天记住词典中所有长度为 \(k\) 的单词。
但是，Keyi 每天的精力是有限的，她一天最多只能学习 \(W\) 个单词，否则她就记不住它们了。
Keyi 不确定要如何有效地安排学习计划，以便尽量用最少的天数完成《维克多词典》的记忆。因此，她恳请您的帮助。
$Input$第一行包含两个整数 \(n\) 和 \(W\ (1\le W \le n \le 50000)\)，表示《维克多词典》内单词的数量以及 Keyi 每天最多学习的单词数量。
第二行包含 \(n\) 个整数 \(a_i\ (1 \le a_i \le 13)\)，\(a_i\) 表示第 \(i\ (1 \le i \le n)\) 个单词的长度。
保证对于相同长度的单词，它们不会出现超过 \(W\) 次。
$Output$输出一行表示 Keyi 记住整本《维克多词典》所需的最少天数。
\(Sample\)
5 4
1 2 1 2 1
——————
2
思路：首先离散化下给的数，对数的数量进行排序。
从大角度来看，出现数量的最多数我怎么都得拿，所以我首先第一个考虑大数，因为小数可能可以和某个大数一起学习掉。
选定一个大数后，对于剩下空间进行一维背包（能填满就填满，为后面的数创造便利），但是得大的先放，因为对于\(100\)，\(99和1\)，显然拿\(100\)先拿就好，于是背包时不取等号
如此进行下来，即可得到最优答案
注意：如果不排序，一定会有错，这个\(QOJ\)已经上传新的\(hack\)数据了,\(CSG\)不清楚
\(hack\)数据：
57 19
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 7 8 8 8 8 9 9 9
答案是3
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<deque>
#include<cctype>
#include<string.h>
#include<math.h>
#include<time.h>
#include<random>
#include<stack>
#include<string>
#define ll long long
#define lowbit(x) (x & -x)
#define endl "\n"
using namespace std;
mt19937 rnd(time(0));
const ll mod=1e9+7;
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
{
ans=ans%mod*(x%mod)%mod;
}
x=x%mod*(x%mod)%mod;
y>>=1;
}
return ans;
}
ll gcd(ll x, ll y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
bool cmp(ll x,ll y){
return x>y;
}
ll a[550000];
ll b[550000];
ll dp[550000];
ll wz[550000];
set<ll>q[50005];
int main()
{
fio();
ll n,m;
set<ll>f;
cin>>n>>m;
for(ll i=1;i<=14;i++)wz[i]=0;
for(ll i=1;i<=n;i++)cin>>a[i],wz[a[i]]++,f.insert(a[i]);
ll cnt=0;
for(auto j:f)
{
cnt++;
b[cnt]=wz[j];
}
sort(b+1,b+1+cnt,cmp);
ll ans=0;
for(ll i=1;i<=cnt;i++)
{
if(b[i]==0)continue;
else
{
ans++;
for(ll i=0;i<=m;i++)q[i].clear(),dp[i]=0;
for(ll k=i+1;k<=cnt;k++)
{
for(ll j=m-b[i];j>=b[k];j--)
{
if(dp[j]<dp[j-b[k]]+b[k])
{
dp[j]=dp[j-b[k]]+b[k];
q[j].clear();
q[j].insert(q[j-b[k]].begin(),q[j-b[k]].end());
q[j].insert(k);
}
}
}
//cout<<dp[m-b[i]]<<endl;
for(auto j:q[m-b[i]])
{
b[j]=0;
}
b[i]=0;
}
}
cout<<ans<<endl;
}