寒假训练第四周
第一天
cf排位赛
C. Constructive Problem
大意：
给定n,得到0~n-1的升序列，要求构造一个序列，使第i个原序列出现的次数等于构造序列第i个的值。
思路：
手玩找规律
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e5+10;
const int mod=1e9+7;
int main()
{
int n;
cin>>n;
if(n<=3||n==6)cout<<-1;
else if(n==4)cout<<"1 2 1 0";
else if(n==5)cout<<"2 1 2 0 0";
else if(n==7)cout<<"3 2 1 1 0 0 0 ";
else{
cout<<n-4<<' '<<"2 1";
for(int i=1;i<=n-7;i++)cout<<" 0";
cout<<" 1 0 0 0";
}
return 0;
}
G. Generate 7 Colors、
大意：
给定0~6的固定序列，再给出数字需出现的次数，问需要几段固定序列（固定序列必须从头取，可取任意长度）
思路：
必须达到固定序列的循环节才可以合并，否则都得重新再取，
因此将循环节开头数字出现次数减去结尾的即可，
注意至少为1.
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e5+10;
const int mod=1e9+7;
ll a[10];
int main()
{
int t;
cin>>t;
while(t--){
for(int i=0;i<7;i++){
scanf("%d",&a[i]);
}
bool flag= false;
for(int i=0;i<6;i++){
if(a[i]<a[i+1]){
printf("-1\n");
flag= true;
break;
}
}
if(!flag){
printf("%lld\n",max(1ll,a[0]-a[6]));
}
}
return 0;
}
E.quality
大意：
给定数组a,和子序列长度k，每次操作可让a中子序列都变成该序列中最小的值，问至少几次操作使数组中所有数相同。
思路：
易得最后数组中全为最小值，
从左向右考虑，碰到不是最小值时 ，从这个 数 开始，往右使用若 干段长度 k 的区间相扣，直到某一段长度 k 的区间内含有 最小值 时才停 止。 如果右边完全没有 最小值，则直接从左侧最近的 非最小值 开始往右以 k-1 为步 长扩展。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e5+10;
const int mod=1e9+7;
ll a[10];
int main()
{
int t;
cin>>t;
while(t--){
for(int i=0;i<7;i++){
scanf("%d",&a[i]);
}
bool flag= false;
for(int i=0;i<6;i++){
if(a[i]<a[i+1]){
printf("-1\n");
flag= true;
break;
}
}
if(!flag){
printf("%lld\n",max(1ll,a[0]-a[6]));
}
}
return 0;
}
K. Klee and Bomb
大意：
给定n个爆竹和各自的颜色，再给定m个连接关系，若互相链接的爆竹颜色相同则可以被互相引爆。自选爆炸点，最多可以选一个爆竹调换成任意颜色，问最多可以爆炸几个爆竹。
思路：
把可互相引爆的爆竹纳入一个加权并查集（此处是集合大小），
先考虑一个爆炸点，算出它的爆炸大小，再对于与它相连但颜色不同爆炸集，分别考虑把当前爆竹换成其他颜色可产生的爆炸大小，取最值。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int fa[N],c[N],sz[N];
vector<vector<int>> e(N);
int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
fa[x]=y;
sz[y]+=sz[x];
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&c[i]);
fa[i]=i;
sz[i]=1;
}
while(m--){
int u,v;
scanf("%d%d",&u,&v);
if(c[u]==c[v]){
merge(u,v);
}
else {
e[u].push_back(v);
e[v].push_back(u);
}
}
int res=0;
for(int u=1;u<=n;u++){
map<int,int> M,vis;
for(int v:e[u]){
v=find(v);
if(vis[v])continue;
vis[v]=true;
M[c[v]]+=sz[v];
}
res=max(res,sz[find(u)]);
for(auto t:M){
res=max(res,t.second+1);
}
}
cout<<res<<endl;
return 0;
}
第二天
记忆宏
Function
大意：
给定递归函数，不允许调用多次
思路：
记忆化，用数组存储答案，
记忆宏+三目运算符大幅减少代码。
记忆宏本质还是宏替换，只是宏中的变量可以被赋值，
注意三目运算符最外边要加上括号。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e5+10;
const int M=4*N;
const int mod=1e9+7;
ll arr[25][25][25];
#define W(a,b,c) (arr[a][b][c]?arr[a][b][c]:arr[a][b][c]=w(a,b,c))
int w(ll a,ll b,ll c){
if (a<=0||b<=0||c<=0) return 1;
if(a>20||b>20||c>20) return W(20,20,20);
if(a<b&&b<c)return W(a,b,c-1)+W(a,b-1,c-1)-W(a,b-1,c);
else return W(a-1,b,c)+W(a-1,b-1,c)+W(a-1,b,c-1)-W(a-1,b-1,c-1);
}
int main(){
while(1) {
ll a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
if(a==-1&&b==-1&&c==-1)break;
ll ans= w(a,b,c);
printf("w(%lld, %lld, %lld) = %lld",a,b,c,ans);
cout<<endl;
}
return 0;
}
加权并查集
银河英雄传说
大意：
两种操作，合并军队，与查询两个战舰间有多少支战舰
思路：
并查集权是集合大小
代码：
#include <bits/stdc++.h>using namespace std;
#define ll long long#define endl '\n'const int N=1e5+10;
const int mod=1e9+7;
int t,f[30005],value[30005],num[30005];
int find(int k){
if(f[k]==k)return f[k];
int fa=find(f[k]);
value[k]+=value[f[k]];
return f[k]=fa;
}
int main(){
for(int i=1;i<=30000;i++){
f[i]=i;num[i]=1;
}
cin>>t;
while(t--){
char c;int x,y;
cin>>c>>x>>y;
int f1=find(x),f2=find(y);
if(c=='M'){
f[f1]=f2;
value[f1]+=num[f2];
num[f2]+=num[f1];
}else{
if(f1!=f2)cout<<-1<<endl;
else cout<<abs(value[x]-value[y])-1<<endl;
}
}
return 0;
}
第三天
cf排位赛
J. Substring Inversion (Easy Version)
大意：
给定一个字符串，构造字串A，B，要求A字典序大于B，并且，B的首字符在A的后，求共有多少对。
思路：
字符串暴力，一个个枚举。
按从小到大排序，出现过的标记，后面的在首字符后加上标记数量。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e5+10;
const int mod=1e9+7;
vector<pair<string,int>> v;
ll sum[410];
int main()
{
int T;cin>>T;
while(T--){
v.clear();
int n;cin>>n;
string s;cin>>s;
for(int i=0;i<n;i++){
sum[i]=0;
string tem="";
for(int j=i;j<n;j++){
tem+=s[j];
v.emplace_back(tem,i);
}
}
sort(v.begin(),v.end());
ll ans=0;
for(int f=0;f<v.size();f++){
int fl=v[f].second;
for(int k=fl+1;k<n;k++){
ans=(ans+sum[k])%mod;
}
sum[fl]++;
}
cout<<ans<<endl;
}
return 0;
}
H.Distance
大意：
给定多条线段，求一个中间点使到各个线段的距离都最短，并求和。
思路：
对顶堆维护中点
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e5+10;
const int mod=1e9+7;
priority_queue<int,vector<int>,less<int>> q1;
priority_queue<int,vector<int>,greater<int>> q2;
int main()
{
int n;
ll ans=0;
cin>>n;
q1.push(-1e9-10);
q2.push(1e9+10);
for(int i=1;i<=n;i++){
int l,r;scanf("%d%d",&l,&r);
if(r<q1.top()){
ans+=q1.top()-r;
q2.push(q1.top());
q1.pop();
q1.push(l);
q1.push(r);
}else if(l>q2.top()){
ans+=l-q2.top();
q1.push(q2.top());
q2.pop();
q2.push(l);
q2.push(r);
}else {
q1.push(l);q2.push(r);
}
printf("%lld\n",ans);
}
return 0;
}
第四天
简单背包总结
1.完全背包
问题：
考虑有 n 种物品，第 i 种物品的每个重量为 wi，价值为 vi，有无限多个。 我们手头有一个大小为 m的背包，需要算出能装下的最大总价值。
思路：
设体积为j，f[j]表示体积为j时的最大价值。
易得大体积的最大价值可由小体积的最大价值推出。
代码：
for (int i = 1; i <= n; ++i) {//枚举物品
for (int j = w[i]; j <= m; ++j) {//枚举能装得下物品的体积
f[j] = max(f[j], f[j - w[i]] + v[i]); //正序，物品可以无限取
}
//对每个物品考虑所有的体积情况
另一种代码：
for (int i = 0; i <= m; ++i) {//枚举体积
for (int j = 1; j <= n; ++j) {//枚举物品
if (i - w[j] >= 0)
f[i] = max(f[i], f[i - w[j]] + v[j]);
} //对每个体积考虑最优物品
}
注：
第二种代码与分组背包比较，
都是考虑每个体积最优的物品，
完全背包从前往后推，一种物品可能不只取1个。
分组背包从后往前推，倒序后每种物品只取1个，对每一组的物品取最优后满足组内互斥。
2.01背包
问题：
考虑有 n 种物品，第 i 种物品的每个重量为 wi，价值为 vi。 每种物品只有 1 件。 有一个大小为 m的背包，需要算出能装下的最大总价值。
思路：
对完全背包进行个数为1的限制。
由于从前往后推会出现多取，
那么从后往前（即倒序），前面全是未取的情况，故可以做到只取1个。
代码：
for (int i = 1; i <= n; ++i) { for (int j = m; j >= w[i]; --j) {// 倒序！！！ f[j] = max(f[j], f[j - w[i]] + v[i]); } }
3.多重背包（朴素版）
问题：
考虑有 n 种物品，第 i 种物品的每个重量为 wi，价值为 vi。 第 i 种物品最多能取 ci 件。 有一个大小为 m的背包，需要算出能装下的最大总价值。
思路：
01背包的升级，个数不为1的限制。
代码：
for(int i=1;i<=n;i++){
for(int l=1;l<=a[i];l++)//个数限制，多个01背包
for(int j=tz;j>=l*t[i];j--) //倒序,前面确定的不要循环到（小优化）
{
dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
}
}
4.二维费用背包
基本与一维处理方式相同，只是物品属性多了1个，需要二维数组。
代码：
for(int i=1;i<=n;++i)
for(int j=mv;j>=v[i];--j)
for(int k=mw;k>=w[i];--k)
dp[j][k]=max(dp[j][k],dp[j-v[i]][k-w[i]]+c[i]);
5.混合背包
最简单的是不同背包分开处理，
或者多重1背包当成限制个数不为1的01背包.
6.分组背包
组内物品互斥，
考虑先处理同1组的物品，确定好每个位置最优的同组物品，再考虑其他组。
代码：
for(int k=1;k<=num;k++)//枚举每一组
for(int j=m;j>=0;j--)//枚举体积
for(int i=1;i<=d[k];i++)//枚举同组内的每个物品
{
int xx=dp[k][i];
if(j>=w[xx])
f[j]=max(f[j],f[j-w[xx]]+vis[xx]);
}
第五天
牛客训练营第六期
B.阿宁的倍数
大意：
一个长度为n的数组a，下标从1开始，有q次操作。
修改操作：数组末尾增加一个数x，数组长度加1。
询问操作：有多少个i(i>x)i(i > x)i(i>x)，满足ai是ax的倍数？
代码：
# include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> fac[N];
vector<int> pos[N];
int main(){
for(int i = 1;i < N;++i){
for(int j = i;j<N;j+=i){
fac[j].push_back(i);
}
}
int n,q;
cin>>n>>q;
vector<int> a(n+1);
for(int i = 1;i <= n;++i){
cin>>a[i];
for(auto v:fac[a[i]]) pos[v].push_back(i);
}
while(q--){
int op,x;
cin>>op>>x;
if(op == 1){
n++;
a.push_back(x);
for(auto v:fac[x]) pos[v].push_back(n);
}
else{
int val = a[x];
int p = (upper_bound(pos[val].begin(),pos[val].end(),x)-pos[val].begin());
int ans = pos[val].size()-p;
cout<<ans<<endl;
}
}
return 0;
}
D.阿宁的毒瘤题
大意：
给定一个字符串，修改其中一个字符，使得udu的子序列最少。
思路：
对于每个位置的字符，算出与它关联的udu子序列个数，改掉最多的那个。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 3 + 2e5;
char s[N];
LL cnt[N];
LL preu[N], sufu[N];
int main() {
cin >> s + 1;
int n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
preu[i] = preu[i - 1];
if (s[i] == 'u') {
++preu[i];
}
}
for (int i = n; i >= 1; --i) {
sufu[i] = sufu[i + 1];
if (s[i] == 'u') {
++sufu[i];
}
}
for (int i = 1; i <= n; ++i) {
if (s[i] == 'd') {
cnt[i] = preu[i - 1] * sufu[i + 1];
}
}
LL u = 0, d = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] == 'u') {
++u;
cnt[i] += d;
} else if (s[i] == 'd') {
d += u;
}
}
u = 0;
d = 0;
for (int i = n; i >= 1; --i) {
if (s[i] == 'u') {
++u;
cnt[i] += d;
} else if (s[i] == 'd') {
d += u;
}
}
LL temp = 0;
for (int i = 1; i <= n; ++i) {
temp = max(temp, cnt[i]);
}
for (int i = 1; i <= n; ++i) {
if (temp == cnt[i]) {
s[i] = 'a';
break;
}
}
cout << s + 1 << endl;
return 0;
}
第六天
倍增的应用——ST表
任意整数可以表示成若干个2的次幂项的和，
因此可划分区间，高效地访问每一个整数。
ST表简单用于静态区间求最值，以及一些区间可以重复贡献的问题。
建议先预处理出2的幂，
for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
代码：
#include <bits/stdc++.h>using namespace std;
#define ll long long#define endl '\n'const int N=1e5+10;
const int M=4*N;
const int mod=1e9+7;
ll f[N][35];
int lg[N];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&f[i][0]);
lg[1]=0;
for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
for(int j=1;j<=lg[n];j++){
for(int i=1;i<=n-(1<<j)+1;i++){
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
int len=lg[r-l+1];
printf("%lld\n",max(f[l][len],f[r-(1<<len)+1][len]));
}
return 0;
}