T1
题面
解题
- 首先，不用考虑相消的字符是哪两种。因为只要有两种不同的字符存在，便一定存在一种途径使得其中一种字符被消完；换言之，一种字符只要还存在的话，就有办法与其他字符进行相消。
- 其次，考虑怎么消字符会使得剩余字符最少，可以当作两列的“堆馒头”问题，其中保证同一高度的两个馒头一定不同。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define endl "\n"
int n,num[30];
void solve()
{
string s;
rep(i,1,26) num[i]=0;
cin>>n>>s; int maxn=0;
rep(i,0,n-1) num[s[i]-'a'+1]++,maxn=max(maxn,num[s[i]-'a'+1]);
cout<<max(2*maxn-n,n%2)<<endl;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--) solve();
return 0;
}
T2
题面
解题
- 欲按位分析，发现按位分析的最大障碍是可进位。但不能主观臆断，需要证明可进位的存在性，最终发现不可进位，故按位分析。
代码
点击查看代码
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define pre(i,a,n) for(int i=n;i>=a;i--)
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
int n;
void solve()
{
cin>>n;
ll ans=1;
while(n)
{
int d=n%10; n/=10;
int mul=0;
rep(i,0,d)
rep(j,0,d) if(d-i-j>=0) mul++;
ans*=mul;
}
cout<<ans<<endl;
return;
}
int main()
{
IOS
int t;cin>>t;
while(t--) solve();
return 0;
}
T3
题面
解题
- Reverse 操作可以反转整个序列，又有 Shift 操作可以将最后一个字符移到序列最前方。故可枚举序列的终点，判断此时序列是否完全非增或非减，是则通过逆变换得到操作次数，注意分情况讨论。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define N int(2e5+10)
int n,a[N<<1],p[N<<1],q[N<<1];
void solve()
{
cin>>n; int ans=1e8;
rep(i,1,n) cin>>a[i],a[n+i]=a[i];
rep(i,1,2*n-1)
{
if(a[i]>=a[i-1]) p[i]=min(p[i-1]+1,n);
else p[i]=1;
if(a[i]<=a[i-1]) q[i]=min(q[i-1]+1,n);
else q[i]=1;
}
if(p[n]==n) ans=0;
else if(q[n]==n) ans=1;
rep(i,n,2*n-1)
{
int k=i-n;
if(p[i]==n)
ans=min(ans,min(n-k,2+k));
if(q[i]==n)
ans=min(ans,min(k+1,n-k+1));
}
cout<<(ans==int(1e8)?-1:ans)<<"\n";
}
int main()
{
IOS
int t=1;cin>>t;
while(t--) solve();
return 0;
}
T4
题面
解题
- 发现只有一个环，故根据贪心，可以先把环外的点处理了。
- 处理环。因为开始遍历的起点有可能将偶数个连续的亮着的灯泡分为两部分奇数个连续亮的灯泡，导致操作次数增加（因为连续的偶数个可以两个两个相消）。故需要变换起点（两个起点在两者的灯泡中可以被当作相邻）跑两次。
代码
点击查看代码
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define pre(i,a,n) for(int i=n;i>=a;i--)
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define pb push_back
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const int maxn=2e5+10;
int n,d[maxn],a[maxn],s[maxn];
void solve()
{
rep(i,1,n) d[i]=0;
cin>>n;
rep(i,1,n)
{
char c;cin>>c;
s[i]=c-'0';
}
rep(i,1,n) cin>>a[i],d[a[i]]++;
queue<int> q; vector<int> res;
rep(i,1,n) if(!d[i]) q.push(i);
while(!q.empty())
{
int u=q.front();q.pop();//cout<<u<<"here"<<endl;
if(s[u])
res.push_back(u),s[u]^=1,s[a[u]]^=1;
d[a[u]]--;
if(!d[a[u]]) q.push(a[u]);
}
vector<int> vis(n+1);
rep(i,1,n)
{
if(!vis[i]&&s[i])
{
vector<int> p,ps;
int x=i,c=0;
while(!vis[x])
{
//cout<<x<<"here"<<endl;
p.push_back(x);
ps.push_back(s[x]); vis[x]=1;
if(s[x]) c++;
x=a[x];
}
//cout<<c<<endl;
if(c%2==1) {cout<<-1<<endl;return;}
int k=p.size();
p.push_back(x),ps.push_back(s[x]);
vector<int> v1,ps1=ps;
rep(j,0,k-1)
if(j==0||ps1[j])
{
v1.push_back(p[j]);
ps1[j]^=1,ps1[j+1]^=1;
}
vector<int> v2,ps2=ps;
rep(j,0,k-1)
if(j!=0&&ps2[j])
{
v2.push_back(p[j]);
ps2[j]^=1,ps2[j+1]^=1;
}
if(v1.size()<v2.size())
for(auto x:v1) res.pb(x);
else for(auto x:v2) res.pb(x);
}
}
cout<<res.size()<<"\n";
for(auto x:res) cout<<x<<" ";
cout<<"\n";
}
int main()
{
IOS
int t;cin>>t;
while(t--) solve();
return 0;
}