昨晚太困了..就没写了..
A题..题意:就是t组数据,然后给你一个n代表你可以操作的数字,然后你可以操作m次,就是可以把ai变成任意数字，结果要你求一段从1开始连续最长的数列..思路:代码很简单..先出现过的地方肯定不要花费了,就是补下没出现过的地方就好了..然后判断下最后能连到哪个数就是答案
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 132913423039
typedef long long ll;
const ll mod=1e9+7;
const ll N=1e2+5;
const int max_=1e5+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x) { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
int a[N];
int cnt[300];
int main()
{
ios;
int t,n,m;
cin>>t;
while(t--)
{
int ans=0;
memset(cnt,0,sizeof(cnt));
cin>>n>>m;
for(int i=1;i<=n;i++) {cin>>a[i];cnt[a[i]]=1;}
sort(a+1,a+1+n);
for(int i=1;m>=0;i++)
{
if(cnt[i]) ans++;
else { if(m>0) ans++,m--; else break;}
}
cout<<ans<<endl;
}
return 0;
}
B题..题意:t组数据,输入n个数,问你有多少种相邻的子段是1 2 3 4 5(从1~任意数)顺序可以乱的..输出种类数,还有每个子段的最大值,假如有个子段不符合就输出-1..
思路:因为题目要求就2个嘛...那么这个题目就变简单了..只要你对->方向扫一下,然后对<-方向扫一下...其实写了一个方向第二个方向复制就好了..如何判断是不是满足条件呢..就只要断开一下第二次出现重复的位子..假如那个位子之前满足题目要求..那我进行下一步寻找..反正最多找两次.细节的地方代码都有注释的..比较简单
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 132913423039
typedef long long ll;
const ll mod=1e9+7;
const ll N=2e5+5;
const int max_=1e5+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x) { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
int a[N];
int b[N];
map<int,int>mp;
int main()
{
ios;
int t;
cin>>t;
while(t--)
{
mp.clear();
int i,n,flag1=1,flag2=1,ans1,ans2,ans3,ans4;//一开始假设正向和反向都存在
cin>>n;
for(i=1;i<=n;i++) cin>>a[i];
for(i=1;i<=n;i++) b[i]=a[n-i+1];//建立反向数组
for(i=1;i<=n;i++)//正向
{
if(mp[a[i]]) break;
else mp[a[i]]=1;
}
int id=i-1;ans1=id;//到这个位子了
if(id==n+1) flag1=0,flag2=0;//假如没有重复的,那么一定不成立
for(i=1;i<=id;i++)//正向
{
if(!mp[i]) flag1=0;// 假如没有出现过
}mp.clear();
for(i=id+1;i<=n;i++)//正向
{
if(mp[a[i]]) break;
else mp[a[i]]=1;
}if(i!=n+1) flag1=0,flag2=0;//假如还出现重复的,那么一定不成立
int id2=n-id;ans2=id2;//到这个位子了
for(i=1;i<=id2;i++)//正向
{
if(!mp[i]) flag1=0;// 假如没有出现过
}mp.clear();
/*反向的处理是一样的*/
for(i=1;i<=n;i++)//反向
{
if(mp[b[i]]) break;
else mp[b[i]]=1;
}
id=i-1,ans4=id;//到这个位子了
if(id==n+1) flag2=0;//假如没有重复的,那么一定不成立
for(i=1;i<=id;i++)//反向
{
if(!mp[i]) flag2=0;// 假如没有出现过
}mp.clear();
for(i=id+1;i<=n;i++)//反向
{
if(mp[b[i]]) break;
else mp[b[i]]=1;
}if(i!=n+1) flag2=0;//假如还出现重复的,那么一定不成立
id2=n-id,ans3=id2;//到这个位子了
for(i=1;i<=id2;i++)//反向
{
if(!mp[i]) flag2=0;// 假如没有出现过
}mp.clear();
if(flag1&&flag2&&(ans1!=ans3)) {cout<<2<<endl;cout<<ans1<<" "<<ans2<<endl;cout<<ans3<<" "<<ans4<<endl;}
else if(flag1) {cout<<1<<endl;cout<<ans1<<" "<<ans2<<endl;}
else if(flag2) {cout<<1<<endl;cout<<ans3<<" "<<ans4<<endl;}
else cout<<0<<endl;
}
return 0;
}C题..题意就是要你给一个长度为n的区间进行染色,注意染色的时候不能超出n的范围,而且要按照指定顺序染色,颜色可以覆盖,要你将m种颜色都染上,m种颜色也有它们的范围,要你求每个合法的染色起点..
思路:首先要判断m个区间加起来是不是>=n的吧，这是染色的前提(小的临界值)...然后呢肯定没种肯定不能太大,也就是没种染色占据1的距离,i+a[i]不能超过n(大的临界值)，有了临界值那么一定可以染色了,怎么染呢?这就是一种不断的放大区间和缩小区间的事了..缩小区间的染色大家应该都会吧..考虑越界..我们这样枚举,事先计算出总长,先试着每种长度枚举为1,看看最远能到哪里,然后判断剩余的+最远的是不是长度<n了...假如小于n了,那我肯定调节一下那块板子的长度..就没了
AC代码
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 132913423039
typedef long long ll;
const ll mod=1e9+7;
const ll N=1e5+5;
const int max_=1e5+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x) { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll ans[N];
ll a[N];
int main()
{
ios;
ll n,m,sum=0,flag=0;
cin>>n>>m;
for(ll i=1;i<=m;i++) {cin>>a[i];sum+=a[i];if(a[i]+i-1>n) flag=1;}
if(sum<n||flag) cout<<-1<<endl;//处理两种边界
else
{
ll g=1;ll maxn=-131,pos;
for(ll i=1;i<=m;i++)
{//sum是后面剩余的长度,maxn为当前最大的
maxn=max(i+a[i]-1,maxn);
sum-=a[i];
if(sum+maxn<=n) {pos=i;break;}
ans[g++]=i;
}
ans[g++]=(n-sum)-a[pos]+1;//他能n-sum的位子
ll cnt=n-sum+1;
for(int i=pos+1;i<=m;i++)
{
ans[g++]=cnt;
cnt+=a[i];
}
for(ll i=1;i<=m;i++) cout<<ans[i]<<" ";cout<<endl;
}
return 0;
}
D题,可能你看了题解会觉得比A还要简单..
题目是给你d和m,然后要求你求满足以下条件的数列有多少个?
- 长度大于1
- 数列里的数递增
- 需要满足b[i] = a[1]^a[2]^...^a[i],b[1] < b[2] < .. < b[n].
问你在1-d的范围内,这样的数列b[i]有多少个?
显然异或递增肯定不能为二进制数位相同的a[i]，考虑最高位同位异或为0,那么一定会递减..所以不能为同位的,然后答案就很简单了,同理异位一定递增,枚举在1-d这个区间的2进制的位数的数量求积就好了..顺带解释一个样例1 7肯定是1,2 3,4 5 6 7这种样子,我们把每一位+个0，那么就可以写成0 1,0 2 3,0 4 5 6 7，那么答案就是235-1..0表示不取,-全部不取的1种情况就是答案了..
代码如下:#include<bits/stdc++.h> #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define pb push_back #define inf 132913423039 typedef long long ll; const ll mod=1e9+7; const ll N=1e5+5; const int max_=1e5+5; const double eps=1e-7; using namespace std; ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);} ll lcm(ll a,ll b) { return a*b/gcd(a,b); } ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;} ll Inv(ll x) { return qp(x,mod-2,mod);} ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;} ll f[32];//打表每个区间个数 int main() { f[0]=1; for(int i=1;i<=31;i++) f[i]=f[i-1]*2; ios; ll t; cin>>t; while(t--) { ll d,m,i,cnt=0,ans=1; cin>>d>>m; for(i=0;d>=f[i];i++);//找到l所在区间并且计算数量 cnt=d-f[i-1]+1; for(ll j=0;j<=i-2;j++) ans=ans*(f[j]+1)%m; ans=(ans)*(cnt+1)%m; cout<<(ans-1+m)%m<<endl; } return 0; }
京公网安备 11010502036488号