Codeforces Round #692 (Div. 2)
按题意模拟
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+500;
int w[N];
int main()
{
int T;
scanf("%d",&T);
// T=1;
while(T--)
{
int n;
scanf("%d",&n);
string s;
cin>>s;
int i;
for(i=n-1;i>=0;i--)
{
if(s[i]!=')') break;
}
int h=i+1;
int q=n-h;
if(h>=q) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}
往后暴力寻找答案,即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+500;
int w[N];bool vis[10];
bool ck(ll x)
{
memset(vis,false,sizeof vis);
ll num=x;
while(x)
{
vis[x%10]=true;
x/=10;
}
for(int i=1;i<=9;i++)
if(vis[i])
{
if(num%i!=0) return false;
}
return true;
}
int main()
{
int T;
scanf("%d",&T);
// T=1;
while(T--)
{
ll n;
scanf("%lld",&n);
while(!ck(n)) n++;
printf("%lld\n",n);
}
return 0;
}
对于一个环来说,它的拆开是需要n+1步的,因为第一步是要拆环,对于不在对角线上也不成环的环每次只需要1步,这里用dsu统计环的数量即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+500;
int fa[N],sz[N];
int vis[N];
int dsu(int u)
{
if(u==fa[u]) return u;
else return fa[u]=dsu(fa[u]);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
int ans=0;
for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1,vis[i]=0;
ans=m;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(x==y)
{
ans--;continue;
}
if(dsu(x)==dsu(y)) vis[dsu(x)]=1;
else sz[dsu(x)]++;
fa[dsu(y)]=dsu(x);
}
for(int i=1;i<=n;i++)
{
if(vis[dsu(i)]==1) ans++,vis[dsu(i)]=2;
}
printf("%d\n",ans);
}
return 0;
}
贪心即可,我们可以知道$填是连续的,对于每一段来说,我们肯定是在前面一段全填1/0,后面一段全填0/1.
假设我们还有一个更优的解法,那么我肯定是交换某个1/0..这样产生的结果(01/10串的数目)是不变的,所以发现只与0/1的数目有关.如此这种处理即是最好做的,因为它会严格的使得某种01/10偏大.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+500;
char s[N];
ll pre_zero[N],suf_zero[N],pre_one[N],suf_one[N],pre[N],suf[N];
ll ans_pzero[N],ans_fzero[N],ans_pone[N],ans_fone[N];
int main()
{
scanf("%s",s+1);
ll x,y;scanf("%lld%lld",&x,&y);
int n=strlen(s+1);
for(int i=1;i<=n;i++)
{
pre_zero[i]=pre_zero[i-1];
pre_one[i]=pre_one[i-1];
pre[i]=pre[i-1];
if(s[i]=='0') pre_zero[i]++;
else if(s[i]=='?') pre[i]++;
else pre_one[i]++;
}
for(int i=n;i>=1;i--)
{
suf_one[i]=suf_one[i+1];
suf_zero[i]=suf_zero[i+1];
suf[i]=suf[i+1];
if(s[i]=='0') suf_zero[i]++;
else if(s[i]=='?') suf[i]++;
else suf_one[i]++;
}
//1.前面填0的答案.
for(int i=1;i<=n;i++)
{
ans_pzero[i]=ans_pzero[i-1];
if(s[i]=='0'||s[i]=='?')
{
ans_pzero[i]+=pre_one[i]*y;
}
else
{
ans_pzero[i]+=(pre_zero[i]+pre[i])*x;
}
}
//2.前面填1的答案.
for(int i=1;i<=n;i++)
{
ans_pone[i]=ans_pone[i-1];
if(s[i]=='1'||s[i]=='?')
{
ans_pone[i]+=pre_zero[i]*x;
}
else
{
ans_pone[i]+=(pre_one[i]+pre[i])*y;
}
}
//3.后面填0的答案.
for(int i=n;i>=1;i--)
{
ans_fzero[i]=ans_fzero[i+1];
if(s[i]=='0'||s[i]=='?')
{
ans_fzero[i]+=suf_one[i]*x;
}
else
{
ans_fzero[i]+=(suf_zero[i]+suf[i])*y;
}
}
//4.后面填1的答案.
for(int i=n;i>=1;i--)
{
ans_fone[i]=ans_fone[i+1];
if(s[i]=='1'||s[i]=='?')
{
ans_fone[i]+=suf_zero[i]*y;
}
else
{
ans_fone[i]+=(suf_one[i]+suf[i])*x;
}
}
//5.统计答案.
ll ans=2e18;
for(int i=0;i<=n;i++)
{
ans=min(ans,ans_pzero[i]+ans_fone[i+1]+(pre_zero[i]+pre[i])*(suf_one[i+1]+suf[i+1])*x+(pre_one[i])*(suf_zero[i+1])*y);
ans=min(ans,ans_pone[i]+ans_fzero[i+1]+(pre_one[i]+pre[i])*(suf_zero[i+1]+suf[i+1])*y+(pre_zero[i])*(suf_one[i+1])*x);
}printf("%lld\n",ans);
return 0;
}
对于这题来说,我们手画一下可以发现:当n>=2时,n项为正,n-1项为负,其他可以任意符号.如此我们可以二进制贪心填充即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+500;
int num[30];
char s[N];
int main()
{
ll n,T;
scanf("%lld%lld",&n,&T);
scanf("%s",s+1);
for(int i=1;i<=n-2;i++)
{
num[s[i]-'a']++;
}
//第n个符号是正,n-1个符号是负.
ll now=(1ll<<(s[n]-'a'))-(1ll<<(s[n-1]-'a'));
T-=now;
for(ll i=25;i>=0;i--)
{
while(T>0&&num[i]) T-=(1ll<<i),num[i]--;
}
for(ll i=25;i>=0;i--)
{
while(T<=-(1ll<<i)&&num[i]) T+=(1ll<<i),num[i]--;
}
if(T) { puts("NO"); return 0;}
bool ans=false;
now=0;
//剩下的数凑完即可.
for(ll i=25;i>=0;i--)
{
if((num[i]&1)&&now==0) now+=(1ll<<i);
else if(now!=0)
{
while(now>=(1ll<<i)&&num[i]) now-=(1ll<<i),num[i]--;
if(num[i]&1) now+=(1ll<<i);
}
}
if(!now) ans=true;
if(ans) puts("YES");
else puts("NO");
return 0;
}
/*
4 7
adaa
*/
待补.
lpt的小屋 文章被收录于专栏
我想要一份甜甜的爱情
