题目链接
解题思路
模拟。
没了。
参考代码
/*
Tips:
你数组开小了吗?
你MLE了吗?
你觉得是贪心,是不是该想想dp?
一个小时没调出来,是不是该考虑换题?
打 cf 不要用 umap!!!
记住,rating 是身外之物。
该冲正解时冲正解!
Problem:
算法:
思路:
*/
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define forll(i,a,b,c) for(re ll i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(re ll i=a;i>=b;i-=c)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define db long double
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define x first
#define y second
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
#define maxqueue priority_queue<ll>
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>
ll pw(ll x,ll y,ll mod){if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;}
void Max(ll&x,ll y){x=max(x,y);}
void Min(ll&x,ll y){x=min(x,y);}
ll _t_;
void _clear(){}
char x,y;
void solve()
{
_clear();
cin>>x>>y;
cout<<x+y-'0'-'0'<<endl;
}
int main()
{
IOS;
_t_=1;
cin>>_t_;
while(_t_--)
solve();
QwQ;
}
题目链接
解题思路
发现每个人都有两张牌。
因此我们发现,我们匹配完了一对牌,那么我们也就可以确定另一对需要匹配的牌。
直接暴力枚举第一对需要匹配的牌然后根据题意统计答案即可。
参考代码
/*
Tips:
你数组开小了吗?
你MLE了吗?
你觉得是贪心,是不是该想想dp?
一个小时没调出来,是不是该考虑换题?
打 cf 不要用 umap!!!
记住,rating 是身外之物。
该冲正解时冲正解!
Problem:
算法:
思路:
*/
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define forll(i,a,b,c) for(re ll i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(re ll i=a;i>=b;i-=c)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define db long double
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define x first
#define y second
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
#define maxqueue priority_queue<ll>
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>
ll pw(ll x,ll y,ll mod){if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;}
void Max(ll&x,ll y){x=max(x,y);}
void Min(ll&x,ll y){x=min(x,y);}
ll _t_;
void _clear(){}
ll a[5],b[5];
void solve()
{
_clear();
forl(i,1,2)
cin>>a[i];
forl(i,1,2)
cin>>b[i];
ll ans=0;
forl(i,1,2)
forl(j,1,2)
{
ll sum=0,sum2=0;
sum+=a[i]>b[j];
sum+=a[3^i]>b[3^j];
sum2+=a[i]<b[j];
sum2+=a[3^i]<b[3^j];
if(sum>sum2)
ans++;
}
cout<<ans<<endl;
}
int main()
{
IOS;
_t_=1;
cin>>_t_;
while(_t_--)
solve();
QwQ;
}
题目链接
解题思路
我们发现一共有 \(m\) 个不空闲的区间,而根据题意,这些区间互不重叠,因此我们肯定是在一个区间的结尾和下一个区间的开头来完成任务。
直接排序后算出两两区间相距长度即可。
注意特判开头和结尾的情况。
时间复杂度 \(O(n \log n)\),瓶颈在于排序。
参考代码
/*
Tips:
你数组开小了吗?
你MLE了吗?
你觉得是贪心,是不是该想想dp?
一个小时没调出来,是不是该考虑换题?
打 cf 不要用 umap!!!
记住,rating 是身外之物。
该冲正解时冲正解!
Problem:
算法:
思路:
*/
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define forll(i,a,b,c) for(re ll i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(re ll i=a;i>=b;i-=c)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define db long double
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define x first
#define y second
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
#define maxqueue priority_queue<ll>
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>
ll pw(ll x,ll y,ll mod){if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;}
void Max(ll&x,ll y){x=max(x,y);}
void Min(ll&x,ll y){x=min(x,y);}
ll _t_;
void _clear(){}
struct node{
ll l,r;
}a[200010];
ll n,m,k;
bool cmp(node x,node y){
return x.l<y.l;
}
ll maxn;
void solve()
{
maxn=0;
_clear();
cin>>n>>m>>k;
forl(i,1,n)
cin>>a[i].l>>a[i].r;
sort(a+1,a+1+n,cmp);
forl(i,1,n)
Max(maxn,a[i].l-a[i-1].r);
Max(maxn,k-a[n].r);
printcf(maxn>=m);
}
int main()
{
IOS;
_t_=1;
cin>>_t_;
while(_t_--)
solve();
QwQ;
}
题目链接
解题思路
因为我们最终所需要的是子序列,因此我们直接用一个指针来指向需要匹配的下一个字符,如果有了,那么将指针向右移动,在指针移动的同时可以顺便求出答案。
时间复杂度线性。
参考代码
/*
Tips:
你数组开小了吗?
你MLE了吗?
你觉得是贪心,是不是该想想dp?
一个小时没调出来,是不是该考虑换题?
打 cf 不要用 umap!!!
记住,rating 是身外之物。
该冲正解时冲正解!
Problem:
算法:
思路:
*/
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define forll(i,a,b,c) for(re ll i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(re ll i=a;i>=b;i-=c)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define db long double
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define x first
#define y second
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
#define maxqueue priority_queue<ll>
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>
ll pw(ll x,ll y,ll mod){if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;}
void Max(ll&x,ll y){x=max(x,y);}
void Min(ll&x,ll y){x=min(x,y);}
ll _t_;
void _clear(){}
string s1,s2;
ll n,m,L;
void solve()
{
L=1;
_clear();
cin>>s1>>s2;
n=s1.size(),m=s2.size();
s1=' '+s1,s2=' '+s2;
forl(i,1,n)
{
if(s1[i]=='?')
{
if(L!=m+1)
s1[i]=s2[L++];
else
s1[i]='a';
}
else
{
if(L<=m && s1[i]==s2[L])
L++;
}
}
if(L==m+1)
{
cfy;
for(auto i:s1)
if(i!=' ')
cout<<i;
cout<<endl;
}
else
cfn;
}
int main()
{
IOS;
_t_=1;
cin>>_t_;
while(_t_--)
solve();
QwQ;
}
题目链接
解题思路
我们发现,我们是一定要先把一个数字变为 \(0\) 才能完成将所有数字变为 \(0\) 的操作的。
因此不难看出,我们肯定是需要把最小的那个数字变成 \(0\) 的。
序列中有一个 \(0\) 之后,我们之后肯定是把乘三操作都丢给这个 \(0\),除以三操作肯定是给不为零的数字,这部分我们可以直接预处理 \(sum_i\) 表示 \(\displaystyle\sum_{i=1}^{n} \left\lceil \dfrac{i}{3} \right\rceil\),预处理后可以实现 \(O(1)\) 时间复杂度查询。
参考代码
/*
Tips:
你数组开小了吗?
你MLE了吗?
你觉得是贪心,是不是该想想dp?
一个小时没调出来,是不是该考虑换题?
打 cf 不要用 umap!!!
记住,rating 是身外之物。
该冲正解时冲正解!
Problem:
算法:
思路:
*/
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define forll(i,a,b,c) for(re ll i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(re ll i=a;i>=b;i-=c)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define db long double
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define x first
#define y second
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
#define maxqueue priority_queue<ll>
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>
ll pw(ll x,ll y,ll mod){if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;}
void Max(ll&x,ll y){x=max(x,y);}
void Min(ll&x,ll y){x=min(x,y);}
ll _t_;
void _clear(){}
ll l,r;
ll sum[200010];
ll f(ll x)
{
ll sum=0;
while(x)
sum++,x/=3;
return sum;
}
void init(){
forl(i,1,2e5+5)
sum[i]=f(i)+sum[i-1];
}
void solve()
{
_clear();
cin>>l>>r;
cout<<sum[r]-sum[l-1]+sum[l]-sum[l-1]<<endl;
}
int main()
{
init();
IOS;
_t_=1;
cin>>_t_;
while(_t_--)
solve();
QwQ;
}
题目链接
解题思路
注意到特殊的数据范围 \(0 \le a_i \le 1\)。
这启示我们写一个依赖当前值域的做法。
由于我们要统计的是子序列,因此我们可以直接枚举选几个 \(0\),而由于题目限制,我们可以直接求出需要选出几个 \(1\),在所有 \(0\) 中选几个,在所有 \(1\) 中选几个,这部分可以通过预处理组合数的方式来解决。
参考代码
/*
Tips:
你数组开小了吗?
你MLE了吗?
你觉得是贪心,是不是该想想dp?
一个小时没调出来,是不是该考虑换题?
打 cf 不要用 umap!!!
记住,rating 是身外之物。
该冲正解时冲正解!
Problem:
算法:
思路:
*/
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define forll(i,a,b,c) for(re ll i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(re ll i=a;i>=b;i-=c)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define db long double
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define x first
#define y second
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
#define maxqueue priority_queue<ll>
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>
void Max(ll&x,ll y){x=max(x,y);}
void Min(ll&x,ll y){x=min(x,y);}
ll _t_;
void _clear(){}
ll n,m,mod=1e9+7;
ll a[200010];
ll pw(ll x,ll y,ll mod)
{
if(x==0)
return 0;
ll an=1,tmp=x;
while(y!=0)
{
if(y&1)
an=(an%mod*tmp%mod)%mod;
tmp=(tmp%mod*tmp%mod)%mod;
y=y>>1;
}
an=an%mod;
return an%mod;
}
ll fac[300010],inv[300010];
void init()
{
fac[0]=1;
forl(i,1,300005)
fac[i]=i*fac[i-1],fac[i]%=mod;
inv[300005]=pw(fac[300005],mod-2,mod);
forr(i,300005,1)
inv[i-1]=inv[i]*i%mod;
}
ll C(ll n,ll m)
{
if(n<m || m<0)
return 0;
return (fac[n]%mod)*(inv[n-m]*inv[m]%mod)%mod;
}
ll ans;
ll sum0,sum1;
void solve()
{
ans=sum0=sum1=0;
_clear();
cin>>n>>m;
forl(i,1,n)
cin>>a[i],sum0+=!a[i],sum1+=a[i];
forl(i,(m+1)/2,m)
ans+=C(sum1,i)*C(sum0,m-i)%mod,ans%=mod;
cout<<ans<<endl;
}
int main()
{
init();
IOS;
_t_=1;
cin>>_t_;
while(_t_--)
solve();
QwQ;
}
题目链接
解题思路
考虑三分。
我们发现,我们每次可以给出两个数字来作为限制。
因此我们可以将这两个数字设为断开区间的点,由于尺子上缺少的数字只有一个,因此我们可以通过每一次询问来减少 \(\dfrac{2}{3}\) 的剩余区间长度。
询问次数 \(\log_3 V\) 次,可以通过 G1 和 G2,其中 \(V\) 为值域。
参考代码
/*
Tips:
你数组开小了吗?
你MLE了吗?
你觉得是贪心,是不是该想想dp?
一个小时没调出来,是不是该考虑换题?
打 cf 不要用 umap!!!
记住,rating 是身外之物。
该冲正解时冲正解!
Problem:
算法:
思路:
*/
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define forll(i,a,b,c) for(re ll i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(re ll i=a;i>=b;i-=c)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//#define endl '\n'
#define QwQ return 0;
#define db long double
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define x first
#define y second
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
#define maxqueue priority_queue<ll>
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>
ll pw(ll x,ll y,ll mod){if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;}
void Max(ll&x,ll y){x=max(x,y);}
void Min(ll&x,ll y){x=min(x,y);}
ll _t_;
void _clear(){}
ll n,m;
ll ans,An;
ll ask(ll x,ll y){
cout<<"? "<<x<<' '<<y<<endl;
ll z;
// An++;
cin>>z;
// z=(x+(x>=ans))*(y+(y>=ans));
return z;
}
/*
8
*/
ll L,R;
void solve()
{
_clear();
L=2,R=999;
while(L<R)
{
ll Mid1=L+(R-L)/3,
Mid2=R-(R-L)/3;
ll now=ask(Mid1,Mid2);
if(now==Mid1*Mid2)
L=Mid2+1;
else if(now==Mid1*(Mid2+1))
L=Mid1+1,R=Mid2;
else
R=Mid1;
}
cout<<"! "<<L<<endl;//<<" queries = "<<An<<endl;
An=0;
}
int main()
{
// IOS;
_t_=1;
cin>>_t_;
while(_t_--)
solve();
// forl(i,2,_t_)
// ans=i,solve();
QwQ;
}
标签:tmp,CF1999,题解,ll,long,define,void,mod
From: https://www.cnblogs.com/wangmarui/p/18347086