第二周

第二周

F. Selling a Menagerie

https://codeforces.com/contest/1872/problem/F

思路

贪心想的话，就是保证弹出一个点时，保证其指向的下一个点存在，就是拓扑序

但是这题给定的条件不能保证 建出的图是有向无环图，所以我们还必须考虑怎么处理环

对环我们怎么处理保证得到的数值最大呢？，因为是环所以我们可以 数值最小的点指向的点开始弹出，直到弹出最小一个点为止，可以证明这样做是最优的。

因为不一定只有一个环所以我们可以把没有弹出的点作为一个集合直到所有点都弹出为止，对于处于不同的环的点，先后顺序是无所谓的

小结

感觉现在遇到的很多输出序列的题很多都是topsort

顺便学到了有环图中处理环的方式

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int N = 100010;
int a[N];
int c[N];
int d[N];
int n;
void solve()
{
	cin>>n;
	for(int i =1;i<=n;i++) d[i] =0;//重新初始化入度
	for(int i = 1;i<=n;i++)
	{
		cin>>a[i];
		d[a[i]]++;
	}
	for(int i =1;i<=n;i++) cin>>c[i];
	
	queue<int> q;
	vector<int> ans;
	set<int> inis;
	//拓扑排序
	for(int i =1;i<=n;i++) if(!d[i]) q.push(i);
	while(q.size())
	{
		int t = q.front(); q.pop();
		ans.push_back(t);
		inis.insert(t);
		d[a[t]]--;
		if(!d[a[t]]) q.push(a[t]);
	}
	//表示没有弹出的点的集合
	set<int> notin;
	
	for(int i = 1;i<=n;i++) if(!inis.count(i)) notin.insert(i);
	//对环的处理
	while(notin.size())
	{
		 int beg = *notin.begin();
		 int cur = beg,mn = beg;
        //找到数值最小的点
		 do
		 {
		 	if(c[cur]<c[mn]) mn = cur;
		 	cur = a[cur];
		 }while(cur!=beg);
		 
		 cur = a[mn];
		 //遍历当前的环
		 do
		 {
		 	ans.push_back(cur);
		 	notin.erase(cur);
		 	cur = a[cur];
		 }while(cur!=a[mn]);
		 
	}
	
	for(auto op: ans) cout<<op<<" ";
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

D. Plus Minus Permutation

思路

直接贪心去想

• 序列中可以取多少个数 cnta
• 序列中可以去多少个数 cntb
• 取的数中有多少是重合的 cntcd

就得到了最后A可以有多少个数,B可以有多少个数，问 的最大值

A就取最大的cnta 个

B就去最小的cntb个

然后等差数列求和即可

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
const int N = 1100;
typedef long long ll;
ll n,x,y;
//gcd模板
ll gcd(ll a,ll b)
{ 
     return b ? gcd(b,a%b) : a;
}

void solve()
{
	cin>>n>>x>>y;
	ll cnt1= n/x;
	ll cnt2= n/y;
	ll me=0;
	ll cd = x*y/gcd(x,y);
	cd = n/cd;//重叠部分就是总长度除以最小公倍数
    cnt1-=cd;
    cnt2-=cd;
    cout<<(n+n-cnt1+1)*cnt1/2 -((cnt2+1)*cnt2/2) <<"\n";//等差数列求和公式
	return ;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	
	return 0;
}

E. Data Structures Fan

思路

前缀异或，我们先观察一下，这题其中的操作

• 对字符串中 的字符进行反转，0变1，1变0
• 问为字符串中0或为1的的下标在 的总的异或值为多少？

我们可以发现其实从头到尾我们并没用对 代表数字的 进行修改，而且是根据其下标在字符串的表示来决定是否用于异或

而且每次 查询的都是全为1或者全为0 的数的异或。因此我们只需要得到当前1的异或或者0的异或就可以用总的异或推出另一个。

可是如何来更新区间呢

这里我们用到了 异或的性质

//q^q==0
//0^q==q

因此假设我们当前使用的是1的异或，当更新区间 时我们就使用 的异或 上 1的异或就可以了

• 因为对于重复出现的会异或为0，也就是从1变为0
• 对于没有出现的会直接异或，也就是从0变为1

符合更新的要求

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
const int N = 100100;
typedef long long ll;
ll sum[N];
ll a[N];

void solve()
{
    int n;
    cin>>n;
    //前缀异或
    for(int i =1;i<=n;i++)
    {
    	 cin>>a[i];
    	 sum[i]=(sum[i-1]^a[i]);
    }
    string op;
    cin>>op;
    string str;
    str+=' ';
    str+=op;
    ll ans =0;
    for(int i = 1;i<=n;i++)
    {
    	if(str[i]=='1')ans^=a[i];
    }
    int q;
    cin>>q;
    while(q--)
    {
    	 int mark;
    	 cin>>mark;
    	 if(mark==1)
    	 {
    	 	int l,r;
    	 	cin>>l>>r;
    	 	l--;
    	 	ans^=(sum[l]^sum[r]);
    	 }
    	 else
    	 {
    	 	 int g;
    	 	 cin>>g;
    	 	 if(g==1) cout<<ans<<" ";
    	 	 else cout<<(ans^(sum[n]))<<" ";
    	 }
    }
    cout<<"\n";
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	
	return 0;
}

E - Mex Min

https://atcoder.jp/contests/abc308/tasks/abc308_e

思路

一开始以为双指针的原因是因为这里求的是全局的最值，而不是局部的最值，当然 用滑动窗口 的话局部和全局应该都是可以得到的。

先取前m个中符合条件的最小值，后面逐步更新就可以了。

小结

• 双指针应该是用于维护全局最值的
• 而滑动窗口偏应用于局部，但是全局应该也是可以的

//滑动窗口模板
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N =1000100;
int w[N];
int q[N];
int n,m;
int r = 1;
int l = 1;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for(int i =1;i<=n;i++) cin>>w[i]; 
    //窗口内最小值
   for(int i =1;i<=n;i++)
   {
   	 while(l<=r&&q[l]<=i-m) l++;
   	 while(l<=r&&w[q[r]]>=w[i]) r--;
   	 q[++r] = i;
   	 if(i-m>=0) cout<<w[q[l]]<<" ";
   }
   
   cout<<"\n";
   l = r = 1;
   //窗口内最大值
   for(int i = 1;i<=n;i++)
   {
   	  while(l<=r&&q[l]<=i-m) l++;
   	  while(l<=r&&w[q[r]]<=w[i]) r--;
   	  q[++r]=i;
   	  if(i-m>=0) cout<<w[q[l]]<<" ";
   }
    return 0;
}

代码

滑动窗口版 100ms

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1500010;
int n,m;
int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 cin>>n>>m;
	 vector<int> a(N);
	 vector<int> cnt(N);
	 int res = n;
	 for(int i = 1;i<=n;i++) cin>>a[i];
	 for(int i = 1;i<=m;i++) 
	 {
	 	 cnt[a[i]]++;
	 }
	 for(int i =0;i<=n;i++)
	   if(cnt[i]==0)
	   {
	   	 res = i;
	   	 break;
	   }	 
	 for(int i =m+1;i<=n;i++)
	 {
	 	cnt[a[i]]++;
	 	cnt[a[i-m]]--;
	 	if(cnt[a[i-m]]==0&&a[i-m]<res) res = a[i-m];
	 }
	 
	 cout<<res<<"\n";
	 
	 
	 return 0;
}

STL偷懒版 1200ms

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 1500010;
int a[N];
int b[N];
int n,m;
set<int> s;
int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 cin>>n>>m;
	 for(int i =1;i<=n;i++) cin>>a[i];
	 for(int i = 0;i<=n;i++) s.insert(i);
	 int ans = n;
	 for(int i = 1,j=1;i<=n-m+1&&j<=n;i++)
	 {
	 	for(;j<=(i+m-1);j++)
	 	{
	        s.erase(a[j]);		
	        b[a[j]]++;
	 	}
	 	ans=min(ans,*s.begin());
	 	if(b[a[i]]==1) s.insert(a[i]);
	 	b[a[i]]--;
	 }
	 cout<<ans<<"\n";
	 return 0;
}

E. Round Dance

思路

题目要中求的是圆圈数量的最大值，最小值。

每个人都至少与一个人相连，所以我们可以用 并查集 来维护那些人是在同一连通块的，最后统计一下当前的连通块数量就是最大值。

那么关于最小值呢？

显然如果要求出最小值，那么就是把上面求的各个连通块尽可能的连在一起就行了。

小结

将所围成的圆圈看为一个个集合，维护集合常用就是用并查集

//好久没见的dsu
//路径压缩模板
int find(int x)
{
    if(x!=p[x]) p[x] = find(p[x]);
    return p[x];
}
//求连通块数量
int cnt= 0;
for(int i = 1;i<=n;i++) if(f[i]==i) cnt++;

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 200010;
int f[N];
int a[N];
int d[N];
//基础并查集
int find(int x) {
  if(x!=f[x]) f[x] = find(f[x]);
  return f[x];
}
//用map来表示，看两个点间是否已经相连，如果已经连好了，就说明两者的入度不需要在加上了
map<pair<int,int>,int> ma;

void solve()
{
    	int n;
    	cin>>n;
    	ma.clear();
    	for(int i = 1;i<=n;i++) f[i] = i,d[i] = 0;
    	
    	for(int i = 1;i<=n;i++)
    	{
    		int x;
    		cin>>x;
    		if(!ma[{i,x}]) 	d[i]++,d[x]++,ma[{i,x}]=ma[{x,i}]=1;//计算每个点的入度
    		if(find(i)!=find(x)) f[find(i)] = find(x);
    	}
    	
    	int sz = 0;
    	int cnt=0;
    	for(int i =1;i<=n;i++) if(i==f[i]) sz++;//求连通块数量
    	for(int i =1;i<=n;i++) if(d[i]==1) cnt++;//求入度为1的点的数量
    	cout<<min(sz,sz-(cnt/2)+1)<<" "<<sz<<"\n"; //最小值就是，将所有可以相连的连在一起，那么就会减去cnt/2个，再加上一个构造出的全新的。
}

int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 int t;
	 cin>>t;
	 while(t--)
	 {
	 	 solve();
	 }
	 
	 return 0;
}

D. Flipper

思路

首先题目中问我们的是，操作一次后的字典序最大是什么样子的。

我们先把整个操作后的序列抽象出来就是，按一般情况看是

一般

显然 我们要先保证 开头为最大值，所以r的确定是非常简单就是找到 p[i+1]==n，那么 R = i

那么我们如何找 l呢来保证最大呢？

既然确定了 这段那么接下来就是要保证 这里最大那么我们就直接从r的位置逆推l的位置

如果当前所选范围为 那么就会是 。。。。 所以如果我们的要 向左走就必须保证必须比 大

就此我们就得到了 的范围了，就是一般情况来说的做法

特判

如果我们的 已经在 的位置了，是可以选择 然后把自己换到第一个的，所以这时我们需要特判，将R = i+1

如果 那么就找 重复以上操作

小结

对于区间置换的话，尝试抽象出结尾状态，然后再就行判断，注意首尾的情况特判

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[2023];
void solve()
{
	int n;
	cin>>n;
	for(int i =1;i<=n;i++) cin>>a[i];
	int r=0;
	for(int i =0;i<n;i++) if(a[i+1]==n) r= i;
	if(r==0)
    {
		for(int i =1;i<n;i++) if(a[i+1]== (n-1)) r=i;
	}
	
	if(r+1==n) r++;
	int l = r;
	for(int i = r-1;i>=1;i--)
	{
		 if(a[i]>a[1]) l--;
		 else break;
	}
	
	for(int i = r+1;i<=n;i++) cout<<a[i]<<" ";
	for(int i = r;i>=l;i--) cout<<a[i]<<" ";
	for(int i = 1;i<l;i++) cout<<a[i]<<" ";
	cout<<"\n";
}
int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 
	 int t ;
	 cin>>t;
	 while(t--)
	 {
	 	 solve();
	 }
}

C. Parity Shuffle Sorting

https://codeforces.com/contest/1733/problem/C

思路

操作简化后的意思就是

• 如果两个数的奇偶不同，那么就改变下标靠大的
• 如果相同，就改变下标较小的

所以我们可以将首尾化做相同的数，然后对于与这个数奇偶不同，那么用最后一个数来改变这个数，

如果相同就用 第一个数来改变这个数。

这样做的话，操作次数就是 次

因为开头首尾操作一次

之后首尾间有 个数，所以再操作 次

所以一共要操作 次

小结

要对CF中的操作要做总结和简化

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N = 200010;

int a[N];
int n,m;

void solve()
{
     cin>>n;
     for(int i =1;i<=n;i++) cin>>a[i];
     
     cout<<(n-1)<<"\n";
     
     if(n-1) cout<<1<<" "<<n<<"\n";
     
     if((a[1]+a[n])%2) a[n] = a[1];
     else a[1] =a[n];
     
     for(int i = 2;i<n;i++)
     {
     	if((a[i]+a[1])%2) cout<<1<<" "<<i<<"\n";
     	else cout<<i<<" "<<n<<"\n";
     }
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int t;
     cin>>t;
	while(t--)
	{
		solve();
	}
	
	return 0;
}

E - MEX

https://atcoder.jp/contests/abc308/tasks/abc308_e

思路

前后缀分解

分解 之前由多少个分别代表 的M

​ 之后有多少个分别代表 的

通过枚举这 这9种可能，然后判断每次加上的数字 O。 加上的数量

因为枚举的数量很少，只有9.所以尽管使用了map遍历也是

小结

对于这类字符串组成相关的，考虑从中间或者前后分解思路，一般易于求数量

顺便学了下这类建立后缀的写法

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 200010;
typedef long long ll;
ll a[N];
char b[N];
map<ll,ll> M,E,X;
int n;

int mex(int x,int y,int z)
{
	int op[3] = {x,y,z};
	sort(op,op+3);
	if(op[0]!=0) return 0;
	if(op[1]!=1&&op[2]!=1) return 1;
	if(op[2]!=2) return 2;
	return 3;
}

int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 cin>>n;
	 for(int i = 1;i<=n;i++) cin>>a[i];
	 for(int i = 1;i<=n;i++) cin>>b[i];
	 
	 for(int i = 1;i<=n;i++) if(b[i]=='X') X[a[i]]++;//建立后缀
	 ll ans =0;//答案
	 for(int i = 1;i<=n;i++)//枚举字符串
	 {
	 	if(b[i]=='M') M[a[i]]++; //建立关于M的前缀
	 	else if(b[i]=='E')//枚举
	 	{
	 		for(auto[fi1, se1]:M)
	 		 for(auto[fi2, se2]:X)
	 		 {
	 		 	ll num = se1*se2;
	 		 	ans+=(num)* mex(fi1,fi2,a[i]);
	 		 }
	 	}
	 	else X[a[i]]--;//更新后缀
	 } 
	 cout<<ans<<"\n";
}

E. Nastya and Potions

https://codeforces.com/contest/1851/problem/E

思路

dfs 直接记忆化搜索，找到每一个点的最小值，药水间有关系，而且不形成环

一个点由自己或和其他点构成

因为 记忆化搜索 时间复杂度为

dfs代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
typedef long long ll;
ll f[N];
int a[N];
int n;
int m;
int h[N],e[N],ne[N],idx,w[N];

void add(int a,int b)//链式向前星
{
	 e[idx] = b;
	 ne[idx] = h[a];
	 h[a] = idx++;
}

ll dfs(int x)
{
	if(f[x]!=-1) return f[x];//如果该点的最小价值已经确定的话，直接返回
	ll ans = 0;
	int fx = 0;
	for(int i = h[x];i!=-1;i=ne[i])//找其相关构成
	{    
	     fx =1;
		 ans+=dfs(e[i]);
	}
	
	if(fx) f[x] = min(ans,1ll*a[x]);//如果有过更新，取min
	else f[x] = a[x];//没有的话，直接赋值给f[x]
	return  f[x];
}
void solve()
{
    	cin>>n>>m;
    	idx = 0;
    	memset(h,-1,sizeof h);
    	for(int i = 1;i<=n;i++)
    	{
    		 cin>>a[i];
    		 f[i] = -1;
    	}
    	
    	for(int i =1;i<=m;i++)
    	{
    		 int x;
    		 cin>>x;
    		 a[x] = 0;
    		 f[x] = 0;
    	}
    	
    	for(int i = 1;i<=n;i++)
    	{
    		int p;
    		cin>>p;
    		for(int j = 1;j<=p;j++)
    		{
    			 int k;
    			 cin>>k;
    			 add(i,k);
    		}
    	}
    	
    	for(int i = 1;i<=n;i++)
    	{
    		 cout<<dfs(i)<<" ";
    	}
    	cout<<"\n";   	
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		 solve();
	}
	
	return 0;
}

思路

每个药水的构成不会找到自己，也就是有向无环图了， 那么我们自然可以想到用 拓扑排序

用拓扑排序来确定每一个点得到的最小代价是多少。

因为每个点价值不是通过买，就是通过合成的，因为保证是有向无环图，所以一定可以找到为入度为0的点，通过拓扑排序得到每一点通过合成的价值，与购买进行取min就可以了

时间复杂度

小结

一个点由其他点构成而且不包括自己，就是指 有向无环图 考虑 DAG，或者 topsort

拓扑代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 200010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int a[N];
ll ans[N];
ll sum[N];
int vis[N];
void add(int a, int b) //链式向前星
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
//拓扑排序
void topsort()
{
     queue<int> q;
    for (int i = 1; i <= n; i ++ )
        if (!d[i]) 
        { 
          q.push(i);      
         }
    //如果这个点是可以无限生产的，就置为0，否则就为a[i];      
    for(int i =1;i<=n;i++)
    {
    	 if(vis[i]) ans[i] = 0;
    	 else ans[i] = a[i];
    }
    
    while (q.size())
    {
        int t = q.front();
                  q.pop();

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            sum[j]+= ans[t];//sum表示当前点由拓扑扩展得到的值
            if (-- d[j] == 0)//当为0时
            { 
                ans[j] = min(ans[j],sum[j]); //sum与最终答案取min
                q.push(j);
            }
        }
    }
  
}

void solve()
{
	cin>>n>>m;
    idx  =0;
    memset(h, -1, sizeof h);
    for(int i = 1;i<=n;i++) 
    {
    	 sum[i] = 0;
    	 vis[i] = 0;
    }

    for(int i = 1;i<=n;i++) cin>>a[i];
    for(int i = 1;i<=m;i++) 
    {
    	  int x;
    	  cin>>x;
    	  vis[x] = 1;
    }
    for(int i = 1;i<=n;i++)
    {
    	 int num;
    	 cin>>num;
    	 for(int j = 1;j<=num;j++)
    	 {
    	 	 int b;
    	 	 cin>>b;
    	 	 add(b,i);
    	 	 d[i]++;
    	 }
    }
    
    topsort();
    
    for(int i = 1;i<=n;i++) cout<<ans[i]<<" ";
    cout<<"\n";
}

int main()
{
	
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		  solve();
	}
	
    return 0;
}

D. Prefix Permutation Sums

https://codeforces.com/contest/1851/problem/D

思路

先判断如果是一个正常的全排列数组去除一个数的话，我们需要考虑下会有怎么样的情况。

• 如果删除的是 首尾 的话，我们只有这个删除的数是没有出现的
• 如果删除的是除了首尾之外的数的话，我们会有两个数没有出现，反而出现一个 出现

我们将 中没有出现的数加入其中，然后把其中多次出现的数，或者不是范围中的数加入其中。

所以我们需要判断

如果加入的数的 大小等于1的话，而且刚好这个数没有出现的话，就是正常的

如果等于3的话将大小排序，如果 而且

如果没有满足条件的话，就是错误的

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 200010;
ll a[N];
int vis[N];
int n;
 vector<ll> w;
int check()
{
	if(w.size()==1) 
	{
		 return !vis[w[0]];
	}
	else if(w.size()==3)
	{
		 return (w[0]+w[1]==w[2]&&!vis[w[0]]&&!vis[w[1]]);
	}
	else return 0;
}
void solve()
{
	  cin>>n;
	  int f = 1;
	  w.clear();
	  for(int i = 1;i<=n;i++) vis[i] =0;
	  for(int i = 1;i<n;i++)
	  {
	  	 cin>>a[i];
	  }
	  for(int i = 1;i<n;i++)
	  {
	  	 ll k = a[i] - a[i-1];
	  	// cout<<k<<"\n";
	  	 if(1<=k&&k<=n&&vis[k]==0)
	  	 {
	  	 	  vis[k] =1;
	  	 }
	  	 else
	  	 {    
	  	 	  w.push_back(k);
	  	 }
	  }
	  for(int i =1;i<=n;i++) if(!vis[i]) w.push_back(i);
	  sort(w.begin(),w.end());
	  f  =  check();
	  if(f) cout<<"YES\n";
	  else cout<<"NO\n";
}
int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 int t;
	 cin>>t;
	 while(t--)
	 {
	 	 solve();
	 }	 
	 return 0;
}

C. Tiles Comeback

https://codeforces.com/contest/1851/problem/C

思路

问是否能构造出一个长度为 可以被 整除， 的每一块都可以是同一颜色的。

其实就是直接从首尾枚举

看从最后一个枚举看能否可以找出至少k块 判断其位置r

从第一个数枚举看是否可以找出至少k块，判断其位置l

然后判断 的位置关系

如果 没有都更新，说明绝对凑不出来要求序列

如果都更新了

• 如果1,n 代表的数一样，那么就一定可以凑出来，
• 如果不一样的话，如果l<r则一定可以，否则一定不可以

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int a[N];
int b[N];
void solve()
{
	 int n,k;
	 cin>>n>>k;
	 for(int i = 1;i<=n;i++)
	 {
	 	 cin>>a[i];
	 }
	 
	 int l = 0;
	 int cntl=0;
	 for(int i = 1;i<=n;i++)
	 {
	 	  if(a[i]==a[1]) cntl++;
	 	  if(cntl%k==0)
	 	  {
	 	  	 l = i;
	 	  	 break;
	 	  }
	 }
	 
	 int r =0;
	 int cntr=0;
	 for(int i = n;i>=1;i--)
	 {
	 	 if(a[i]==a[n]) cntr++;
	 	 if(cntr%k==0) 
	 	 {
	 	 	 r = i;
	 	 	 break;
	 	 }
	 }
	 if(l&&r)
	 {
	 	  if(a[1]==a[n])
	 	  {
	 	  	 cout<<"YES\n";
	 	  }
	 	  else
	 	  {
	 	  	  if(l>r) cout<<"NO\n";
	 	  	  else cout<<"YES\n";
	 	  }
	 }
	 else cout<<"NO\n";
	 
}

int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 int t;
	 cin>>t;
	 while(t--)
	 {
	 	 solve();
	 }
	 return 0;
}

C - AB Substrings

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_c

思路

首先把每个字符串中的 AB 个数加到答案中。 接着，如果只考虑以 A 结尾的字符串（个数记作 a），或者以 B 开头的字符串（个数记作 b），每一对拼起来可以得到一个 AB，那么答案额外加上 min(a,b)。 然后，考虑以 B 开头且以 A 结尾的字符串（个数记作 ba），这些字符串可以「插入」到上面拼起来的 AB 之间，那么答案额外加上 ba+min(a,b)。 除了一种特殊情况：ba > 0 且 a = 0 且 b = 0，此时答案只能加上 ba-1。

或者可以认为

把 BA 插在 AB 之间永远 >= 插在其他地方，所以在有AB的情况下把BA插在 AB之间就是最优解

没有AB的情况下就是BA-1

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 int ba =0;
	 int b =0;
	 int a =0;
	 int n;
	 cin>>n;
	 int cnt = 0;
	 for(int i = 1;i<=n;i++)
	 {
	     string str;
	     cin>>str;
	     int len = str.size();
	     if(str[0]=='B'&&str[len-1]=='A') ba++;
	     else if(str[len-1]=='A') a++;
	     else if(str[0]=='B') b++;
	     for(int i = 0;i<len;i++)
	     {
	     	 if(str[i]=='A'&&str[i+1]=='B') cnt++;
	     }	 
	 }
	 
	 if(a==0&&b==0&&ba!=0) cout<<(cnt+ba-1)<<"\n";
	 else
	 {
	 	 cout<<(cnt+min(a,b)+ba)<<"\n";
	 } 
	 
	 return 0;
}

D - General Weighted Max Matching

https://atcoder.jp/contests/abc318/editorial/7081

思路

状态压缩DP，首先 其实一般就是在暗示状态压缩，或者

爆搜了。

状态表示 表示以n的二进制形式下，可以获得的最大值

比如 二进制下就为 ,就表示了 这四个点已经链接下所获得的最大值

状态转移 枚举当前的 中 的二进制，每一个状态枚举所有未选的点对，然后用或存在得到可以改变的状态是什么

时间复杂度 n<=16,

小结

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 30;
typedef long long ll;
ll dp[1000000];
int d[N][N];
int n;
int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 cin>>n;
	 for(int i = 0;i<n;i++)
	  for(int j =i+1;j<n;j++) cin>>d[i][j];
	  
	  for(int i = 0;i<= (1<<n)-1;i++)
	  {
	  	  for(int j = 0;j<n;j++)
	  	  {
	  	  	 if(i>>j&1) continue;
	  	  	 for(int k =j+1;k<n;k++)
	  	  	 {
	  	  	 	if(i>>k&1) continue;
	  	  	 	int nb = i|(1<<j)|(1<<k);//通过或运算得到可以推导的状态是什么
	  	  	 	dp[nb] =max(dp[nb],dp[i]+d[j][k]);
	  	  	 }
	  	  }
	  }
	  cout<<dp[(1<<n)-1]<<"\n";
	 return 0;
}

优化版

优化了枚举方式，取最小的等于0的点，再枚举其他点就可以了。

因为这样更新也是可以保证全覆盖的

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
ll a[30][30];
ll dp[1<<20];
int n;
void solve()
{
	cin>>n;
	
	for(int i = 0;i<n;i++)
	{
		for(int j = i+1;j<n;j++)
		{
			cin>>a[i][j];
		}
	}
	
	for(int i = 0;i<=(1<<n)-1;i++)
	{
		int l;
		for(int p = 0;p<n;p++)
		{
			if(i>>p&1) continue;
			l = p;
			break;
		}
	
		for(int k =l;k<n;k++)
		{
			
			if(!(i>>k&1)) 
			{ 
			   int ne = i|(1<<l)|(1<<k);
			   dp[ne]=max(dp[ne],dp[i]+a[l][k]);
			}
		}
	}
	cout<<dp[(1<<n) -1]<<"\n";
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	t = 1;
	while(t--)
	{
		solve();
	}
	return 0;
}

C - Blue Spring

思路

将所有天数的票价进行排序，每次统计m个票的总价，判断是否可以用m个一日通票直接替换。

特判，在剩余天数不足m时，在为天数为1时直接判断就可以了

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N =200010;
typedef long long ll;
ll a[N];
int n;
int m,d;
int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 cin>>n>>d>>m;
	 
	 ll sum = 0;
	 for(int i = 1;i<=n;i++)
	 {
	 	 cin>>a[i];
	 	 sum+=a[i];
	 }
	 
	 sort(a+1,a+1+n);
	 int cnt =0;
	 ll ans=0;
	 for(int i = n;i>=1;i--)
	 {
	 	  cnt++;
	 	  ans+=a[i];
	 	  if(cnt==d)
	 	  {
	 	  	  sum = min(sum,sum-ans+m);
	 	  	  cnt=0;
	 	  	  ans = 0;
	 	  }
	 	  else if(i==1&&cnt!=d)
	 	  {
	 	  	   sum = min(sum,sum-ans+m);
	 	  }
	 }
	 cout<<sum<<"\n";
	 
	 return 0;
}

E - Sandwiches

https://atcoder.jp/contests/abc318/tasks/abc318_e

思路

个人感觉本质就是求贡献 ，假设两个下标代表的值相同，该数列为Z。则有

• 当 时说明 是连续的，所以两者间没有其他的点作为 ,这两段的连接点

• 当​ 时说明连续，所以两者间有其他的点作为 ,这两段的连接点，连接点数量为 再乘以左段的数量乘以右段的数量就可以了

  因为题目中数的取值 为 ,数量也为 ，所以我们最多会遍历 个点。遍历的数量为输入的数的数量

  时间复杂度为

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 300005;
vector<int> a[N];
int n;
int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 cin>>n;
	 for(int i = 1;i<=n;i++)
	 {
	 	 int x;
	 	 cin>>x;
	 	 a[x].push_back(i);
	 }
	 ll ans =0;
	 
	 for(int i = 1;i<N;i++)
	 {
	 	if(a[i].size())
	 	{   
	 	    int len = a[i].size();
	 	    int cha=0;
	 	    for(int j =0;j<len-1;j++)
	 	    {
	 	    	if(a[i][j+1] - a[i][j]-1 == 0) continue;
	 	    	cha= a[i][j+1] - a[i][j] -1;
	 	    	ans+=1ll*(j+1)*cha*(len-1-j);
	 	    }
	 	}
	 }
	 cout<<ans<<"\n";
}

小结

• 如果状态压缩DP，或者位运算的时候，注意运算顺序，要么写清楚要么打括号，不然会因为运算顺序可能会有差错
• 同上用到二进制时，所有数组从0开始开头
• string从1开始计数的写法
• 拓扑序，对环的处理
• 的概念 0到n中没有出现的最小非负数
• 滑动窗口模板（从1开始），双指针
• 对于三元组的东西，一般都是从中间开始入手
• 并查集
• 异或的性质
• 对于DP中的转化方程，很多只要保证当前的这一更新方式可以 确保全覆盖的 不会漏就可以了

拓扑排序

当给的边是a 被那些点指向时

void topsort()
{
     queue<int> q;
    for (int i = 1; i <= n; i ++ )
        if (!d[i]) { q.push(i); }
  
    while (q.size())
    {
        int t = q.front();
                  q.pop();

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            sum[j]+= ans[t];//sum表示当前点由拓扑扩展得到的值
            if (-- d[j] == 0)//当为0时
            { 
                ans[j] = min(ans[j],sum[j]); //sum与最终答案取min
                q.push(j);
            }
        }
    }
}

当给出的是 a指向b 时

for(int i =1;i<=n;i++) if(!d[i]) q.push(i);
	while(q.size())
	{
		int t = q.front(); q.pop();
		ans.push_back(t);
		inis.insert(t);
		d[a[t]]--;
		if(!d[a[t]]) q.push(a[t]);
	}

string从1开始

string op;
cin>>op;
string str;
str+=' ';
str+=op;

滑动窗口

//滑动窗口模板
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N =1000100;
int w[N];
int q[N];//存下标
int n,m;
int r = 1;
int l = 1;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for(int i =1;i<=n;i++) cin>>w[i]; 
    //窗口内最小值
   for(int i =1;i<=n;i++)
   {
   	 while(l<=r&&q[l]<=i-m) l++;
   	 while(l<=r&&w[q[r]]>=w[i]) r--;
   	 q[++r] = i;
   	 if(i-m>=0) cout<<w[q[l]]<<" ";
   }
   
   cout<<"\n";
   l = r = 1;
   //窗口内最大值
   for(int i = 1;i<=n;i++)
   {
   	  while(l<=r&&q[l]<=i-m) l++;
   	  while(l<=r&&w[q[r]]<=w[i]) r--;
   	  q[++r]=i;
   	  if(i-m>=0) cout<<w[q[l]]<<" ";
   }
    return 0;
}

并查集

int find(int x)
{
    if(x!=p[x]) p[x] = find(p[x]);
    return p[x];
}
//求连通块数量
int cnt= 0;
for(int i = 1;i<=n;i++) if(f[i]==i) cnt++;

乘法逆元

由于在程序中表示分数，一般就只能用浮点数，但是浮点有误差，所以我们用逆元的代替表示

即 在mo p的情况下满足条件，即称x为 a的逆元，表示

简单证明

费马小定理 对于一个质数p 始终有 在mod 的意义下。

因此有 在 p的意义下

那么 我们只需要求 就可以了，整个我们就可以用快速幂了

举例

求