A. Politics
题意：有n个人对m个决案进行投票，对于每一个决案如果票数相同则所有人都离场，反之票数少的一方离场，现在提前知道了每个人的意见，让一些人参与投票，在保证第一个人不离场的情况下最终剩余人数最多是多少
Solution
把和第一个意见不同的给去掉就行了
void solve()
{
int n,k;cin>>n>>k;
set<int>st;
for(int i=1;i<=n;i++)
{
cin>>s[i];
st.insert(i);
}
int ans=n;
int cnt=0;
for(int i=0;i<k;i++)
{
for(auto it:st)
{
if(s[it][i]!=s[1][i])
{
a[++cnt]=it;
}
}
while(cnt>0)st.erase(a[cnt--]);
}
cout<<st.size()<<"\n";
}
B. Indivisible
题意：构造一个由[1,2,...,n]组成的数组，使得任意一个区间长度大于等于2的区间，其区间和不能被区间长度整除
Solution
打表找找规律，发现直接2,1,4,3,6,5,....,n,n-1构造就行了，奇数是肯定不行的，因为n为奇数时，n+1为偶数，n*(n+1)/2可以被n整除
void dfs(int x) //打表
{
if(x>n)
{
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int sum=0;
for(int k=i;k<=j;k++)
{
sum+=a[k];
}
if(sum%(j-i+1)==0)return;
}
}
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
cout<<"\n";
return;
}
for(int i=1;i<=n;i++)
{
if(vis[i])continue;
vis[i]=1;
a[x]=i;
dfs(x+1);
vis[i]=0;
}
}
void solve()
{
cin>>n;
if(n==1)
{
cout<<"1\n";
return;
}else if(n&1)
{
cout<<"-1\n";
return;
}
for(int i=1;i<=n;i+=2)cout<<i+1<<" "<<i<<" ";
cout<<"\n";
}
C. Almost Increasing Subsequence
题意：定义几乎增加子序列为不存在连续的x,y,z，满足x>=y>=z，给出一个长为n的数组，对其进行q次询问，每次询问输出最长的几乎增加子序列的长度
Solution
前缀和，先处理以a[i]为结尾的三个连续的数是否满足a[i-2]>=a[i-1]>=a[i]
然后用前缀和记录一遍数量，对于每一个询问区间，答案是r-l+1-(s[r]-s[l+1])
说实话我不会证明这个结论的充分必要性，感觉是对的就这么写了(
void solve()
{
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=3;i<=n;i++)
{
if(a[i-2]>=a[i-1]&&a[i-1]>=a[i])vis[i]=1;
s[i]=s[i-1]+vis[i];
}
while(m--)
{
int l,r;cin>>l>>r;
if(r-l+1<3)cout<<r-l+1<<'\n';
else cout<<r-l+1-(s[r]-s[l+1])<<"\n";
}
}
D. Fish Graph
题意：给出一个无向图，问是否存在一个环，环满足环上存在一特殊点，去掉环上的边后，这个特殊点还有至少两条边
Solution
想法就是枚举每个特殊点，看它是否在环上，并且除了环上的边还有两条边
那么这样的点的度一定是>=4的，再就是找环，dfs递归找，一开始是用vector存边，但是后来发现好麻烦，就直接存点
当找到环的时候，我们就通过每个点的父节点把所有的点都存下来，然后再把所有的点都标记为环上的点，再遍历特殊点的其他边
因为答案只需要两个，所以我们也只用遍历两条其他边
然后就...WA了
问题来了，一个特殊点可能在多个环上，不过题目没有对环作出要求，所以我们还需要把环缩小，从特殊点的下一个点的下一个点开始遍历，看是否存在一个点和特殊点之间有边，这样就可以达到缩小环的目的
vector<int>e[N];
int vis[N];
int check[N];
vector<int>c; //存环上的点
int flag=0;
int fa[N];
void dfs(int x,int pre,int st)
{
vis[x]=1;
if(flag)return;
for(auto it:e[x])
{
if(it==pre)continue;
if(flag)return;
if(it==st)
{
int t=x;
while(x!=st)
{
c.push_back(x);
check[x]=1;
x=fa[x];
}
c.push_back(it);
check[it]=1;
flag=1;
return;
}
if(!vis[it])
{
fa[it]=x;
dfs(it,x,st);
}
}
}
void solve()
{
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)e[i].clear();
for(int i=1;i<=m;i++)
{
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
if(e[i].size()<4)continue;
for(int i=1;i<=n;i++)vis[i]=check[i]=fa[i]=0;
c.clear();
flag=0;
dfs(i,0,i);
if(!flag)continue;
for(auto it:e[i])vis[it]=-1;
int sz=2;
for(int i=c.size()-3;i>=0;i--)
{
sz++;
if(vis[c[i]]==-1)
{
break;
}
}
while(c.size()>sz)
{
auto it=*c.begin();
check[it]=0;
c.erase(c.begin());
}
vector<int>tt;
for(auto it:e[i])
{
if(!check[it])tt.push_back(it);
if(tt.size()==2)break;
}
cout<<"YES\n";
cout<<c.size()+2<<"\n";
cout<<tt[0]<<" "<<i<<"\n";
cout<<tt[1]<<" "<<i<<"\n";
int len=c.size();
for(int i=0;i<len;i++)
{
cout<<c[i]<<" "<<c[(i+1)%len]<<"\n";
}
return;
}
cout<<"NO\n";
}