目录
A. Politics
思路
与第 \(1\) 个人的意见不同的人都要删除
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
string t[n];
int res=n;
for(int i=0;i<n;i++)
{
cin>>t[i];
if(t[i]!=t[0])res--;
}
cout<<res<<endl;
}
return 0;
}
B. Indivisible
题意
能否构造一个排列 \(p=[a_1,a_2,…,a_n]\) ，使得对于任何 \(1≤l<r≤n\) ，\(sum=a_l+a_{l+1}+⋯+a_r\) ，都有 \(sum\) 不能被 \(r−l+1\) 整除，即 \(sum\%(r-l+1)\ne 0\)
思路
- 当 \(n=1\) 时，\(p=[1]\)
- 当 \(n\) 为其他奇数时，有 \(\frac{n*(n+1)}{2}\%n=0\) ，不能构造出这样的排列
- 当 \(n\) 为偶数时，可以构造 \([2,1,4,3……n,n-1]\) 这样的一个奇偶相间的排列，证明如下：
- 当 \(l\) 和 \(r\) 奇偶性不同时，\(sum=\frac{(r-l+1)(l+r)}{2}\) ，因为 \((l+r)\%2\ne 0\)，所以 \(gcd(\frac{(r-l+1)(l+r)}{2},r-l+1)=\frac{(r-l+1)}{2}\)，即 \(sum\%(r-l+1)\ne 0\)
- 当 \(l\) 和 \(r\) 奇偶性相同时，
- 当 \(l\) 和 \(r\) 都为偶数时，\(sum=\frac{(r-l+1)(l+r)}{2}-1\) ，\(sum\%(r-l+1)= -1 \ne 0\)
- 当 \(l\) 和 \(r\) 都为奇数时，\(sum=\frac{(r-l+1)(l+r)}{2}+1\) ，\(sum\%(r-l+1)= 1 \ne 0\)
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
if(n==1)
{
puts("1");
continue;
}
if(n%2==1)
{
puts("-1");
continue;
}
for(int i=1,j=2;j<=n;j+=2,i+=2)
cout<<j<<' '<<i<<' ';
puts("");
}
return 0;
}
C. Almost Increasing Subsequence
题意
定义一个序列为 \(almost-increasing\) ，当序列中不包含三个连续的元素 \(x,y,z\) ，并且 \(x≥y≥z\) ，询问区间 \([l,r]\) 中，满足条件的序列最长的长度是多少
思路
对于产生冲突的区间 \([a_{i-2},a_{i-1},a_{i}]\) ，都由 \(a_i\)唯一确定，对于每个查询，用区间总长度 \(r-l+1\) 减去区间内冲突点的个数 \(s[r]-s[l+1]\) 即可
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
vector<int>a(n+1);
vector<int>s(n+1);
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=2;i<=n-1;i++)
if(a[i-1]>=a[i]&&a[i]>=a[i+1])
s[i]=s[i-1]+1;
else s[i]=s[i-1];
while(k--)
{
int l,r;
cin>>l>>r;
int len=r-l+1;
if(len<=2)cout<<len<<endl;
else cout<<len-(s[r-1]-s[l])<<endl;
}
return 0;
}