首页 > 其他分享 >CF1999题解

CF1999题解

时间:2024-08-07 15:19:07浏览次数:12  
标签:tmp CF1999 题解 ll long define void mod

题目链接

CF1999A

解题思路

模拟。

没了。

参考代码

/*
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;
}

题目链接

CF1999B

解题思路

发现每个人都有两张牌。

因此我们发现,我们匹配完了一对牌,那么我们也就可以确定另一对需要匹配的牌。

直接暴力枚举第一对需要匹配的牌然后根据题意统计答案即可。

参考代码

/*
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;
}

题目链接

CF1999C

解题思路

我们发现一共有 \(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;
}

题目链接

CF1999D

解题思路

因为我们最终所需要的是子序列,因此我们直接用一个指针来指向需要匹配的下一个字符,如果有了,那么将指针向右移动,在指针移动的同时可以顺便求出答案。

时间复杂度线性。

参考代码

/*
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;
}

题目链接

CF1999E

解题思路

我们发现,我们是一定要先把一个数字变为 \(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;
}

题目链接

CF1999F

解题思路

注意到特殊的数据范围 \(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;
}

题目链接

CF1999G1

CF1999G2

解题思路

考虑三分。

我们发现,我们每次可以给出两个数字来作为限制。

因此我们可以将这两个数字设为断开区间的点,由于尺子上缺少的数字只有一个,因此我们可以通过每一次询问来减少 \(\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

相关文章

  • 2024.8.7 模拟赛题解
    T1过于简单,不必阐述。T2给定一个仅包含\(A\)和\(P\)的字符串,每次操作可以删除相邻的\(AP\)或者\(PP\),问字符串最后的最小长度。$Sol:$为求最值问题,考虑贪心。先给出考场做法。发现若干的\(P\)是一定能合并掉的,于是贪心策略,就是如何最小化\(A\)的个数。对于每个......
  • 题解:Codeforces Round 964 (Div. 4) A
    A.A+BAgain?timelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputGivenatwo-digitpositiveinteger\(n\),findthesumofitsdigits.InputThefirstlinecontainsaninteger\(t\)(\(1......
  • 【题解】Solution Set - NOIP2024集训Day1 数据结构
    【题解】SolutionSet-NOIP2024集训Day1数据结构https://www.becoder.com.cn/contest/5429「CF1428F」FruitSequences线段树是可以维护区间最长子段的1。记固定右端点在\(i\),的答案为\(f_i\)。那么:\(a_i=0\),\(f_i=f_{i-1}\);\(a_i=1\),打一个单调栈维护所有的最长子......
  • 题解:P10543 [THUPC 2024 决赛] 黑白
    好题。题意\(n\timesm\)的网格图初始每个格子有黑有白,两人轮流操作,每次选择一个白格染黑。操作后不能存在一条\((1,1)\)到\((n,m)\)的路径,否则本次操作者输,另一人赢。思路首先判断是否一上来就输了。易发现到最后一定会操作到只剩一条道路,设路径长度为\(s\),那么\(s\)......
  • 题解:UVA11181 条件概率 Probability|Given
    主要思路:概率期望。首先可以发现\(n\)的数据极小。然后我们设\(a\)为为每个人买东西的情况,\(b\)为当有\(b\)个人去时的情况。大家都应该知道条件概率式子为\(P(a|b)=\frac{P(ab)}{P(b)}\)。然后暴力搜索\(P(ab)\)和\(P(b)\)。其实这道题有复杂度更低的dp做法,但......
  • 题解:CF1896G Pepe Racing
    主要思路:构造。思路方法一一个一个的找,分别查询\([1,n],[n+1,2n],\dots,[n(n-1)+1,n^{2}]\)中最快的人,再把\(n\)个人合起来查询,不过很明显的是,这个方法很蠢,并不能切掉此题。方法二找第二快的人,只有最快的人在的一组需重新询问,剩下答案无需改变。需排除的人的一组用不是现......
  • 2024牛客暑期多校训练营7 C Array Sorting 题解
    乱搞非正解写法。分类讨论各种情况。降序排序对应交换即可数组个数小直接考虑相邻的交换其他都看做随机数据考虑结合前面情况,很容易想到,先把数组变成一个尽量有序的数组(每个元素和自己正确的位置相差不大)。最后再多次相邻交换,使得每个元素都在正确位置。把数组变成......
  • 洛谷 P4910题解
    题目大意现在穿T次手串,每根手串的长度分别为不同的n,有木和金两种珠子,相邻两颗珠子必须有一个是金。题目思路分析我们现在设穿到第n个珠子时用金的方案数为f[1][n],用木的方案数为f[0][n]如果第n个珠子为金,那么前一颗珠子是什么都可以,因此f[1][n]=f[1][n-1]+f[0][n-1]而如果......
  • CF573E Bear and Bowling 题解
    Description给定一个长度为\(n\)的序列\(a_{1\dotsn}\)。你要求一个\(a\)的子序列\(b_{1\dotsm}\)(可以为空),使得\(\sum_{i=1}^mib_i\)的值最大。\(n\le10^5\),\(|a_i|\le10^7\)。Solution有一个显然的dp是设\(f_{i,j}\)表示前\(i\)个数,选\(j\)个数的......
  • CF1920D题解
    题面这里不再赘述了,直接搬个链接。InLuoguInCodeforces思路存储一共两种操作:要么在末尾加一个数xxx,要么把整一段复制......