A. Dreamoon and Ranking Collection
A题大家应该都没啥问题叭QAQ 题意就是已经比赛了n场 n场的场次都已经告诉了你 问你再比x次 问你你最大的名次是多少（这个最大的名次是指 1-当前名次都已经拿过了）然后注意数据范围 n,x<=100 所以最多可以到两百名呢 所以记得数组要开200多一点
（呜呜我的代码日常很长 所以手速很慢
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t;
cin>>t;
while (t--){
int n,x;
scanf("%d%d",&n,&x);
int a[105];
int visit[205]={0};
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
visit[a[i]]=1;
}
int flag=0;
for (int i=1;i<=205;i++){
if (visit[i]==0){
visit[i]=1;
x--;
}
if (x==0)
break;
}
for (int i=1;i<=205;i++)
{if (visit[i]==1)
flag=i;
else
break;}
cout<<flag<<endl;
}
return 0;
}
B. Dreamoon Likes Permutations
啊啊这题一看就是一个模拟题某 我觉得群里另一个巨佬的思路应该更好 用前缀和
但在这里就拙劣的讲一下我的思路叭。我是先找左边的1位置计为l吧 右边的1计位r 然后i从l开始到r-1 开始找 如果某一个位置满足了第1到第i个位置满足了 是1-i的排列 那我就先记录下来 然后我在去判断每一个已经记录的位置 右边是不是也是1-（n-i）的排列 然后最后输出就好
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t;
cin>>t;
while (t--){
int a[200005];
int n,l=0,r=0,visit1[200005]={0},visit2[200005]={0};
int ccount1=0,ccount2=0,mx1=1,mx2=1;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if (a[i]==1)
{
if (l==0)
l=i;
else
r=i;
}
}
for (int i=l;i>=1;i--){
if (visit1[a[i]]==0){
visit1[a[i]]=1;
ccount1++;
mx1=max(mx1,a[i]);
}
}
for (int i=r;i<=n;i++){
if (visit2[a[i]]==0){
visit2[a[i]]=1;
ccount2++;
mx2=max(mx2,a[i]);
}
}
int ans1[200005]={0},ans=0,tot=0;
for (int i=l;i<r;i++){
if (visit1[a[i]]==0){
visit1[a[i]]=1;
ccount1++;
mx1=max(mx1,a[i]);
}
if (mx1==ccount1&&mx1==i){
ans1[++tot]=i;
}
}
int now=r,m=tot;
int check[200005]={0};
for (;tot!=0;tot--){
for (int i=now;i>ans1[tot];i--){
if (visit2[a[i]]==0){
visit2[a[i]]=1;
ccount2++;
mx2=max(mx2,a[i]);
}
}
if (mx2==ccount2&&mx2==n-ans1[tot]){
{check[tot]=1;
ans++;
}
}
now=ans1[tot];
}
cout<<ans<<endl;
for (int i=1;i<=m;i++){
if (check[i]==1){
cout<<ans1[i]<<" "<<n-ans1[i]<<endl;
}
}
}
return 0;
}
C. Dreamoon Likes Coloring
这题先告诉大家可以用贪心来写
题意: 总共有n的小房间 然后你要涂m次颜色 第i次涂的长度已经告诉你 而且每次涂的长度不能浪费 比如这次要涂的长度是5 你就不能去涂倒数四个位置 然后最后保证全部的颜色都能出现 而且所有的房间都被涂过了
思路：我记录了所有涂的长度为sum 然后贪心的来讲吧 比如sum很大 比n大很多 那假如第一次涂的长度是10 那我们第二次在2这个位置涂的话 那是不是sum减去第一次的长度变成了sum-10 然后我们要涂的长度变成了n-1 那么sum就会向n靠近 （sum如果比n小那就肯定不行了） 然后每次涂的时候判断一下 比如我第一次涂10 那么我第二次是要在2 还是3 还是其他位置涂呢 最后n=sum的时候 就一直连着涂就好
ps 我的代码很长 我总想把一些已知的情况给去掉先 请大家多多包涵
如果要走我的思路的话 循环求a[i].ans的 可以自己好好推一下 理解一波
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int val,ans;
}a[100005];
int main() {
int n,m,flag=0;
ll sum=0;
cin>>n>>m;
for (int i=1;i<=m;i++)
{scanf("%d",&a[i].val);
if (i+a[i].val-1>n)
flag=1;
sum+=a[i].val;
}
if (flag){
cout<<"-1"<<endl;
return 0;
}
if (m>n||sum<n){
cout<<"-1"<<endl;
return 0;
}
int now=1;
for (int i=1;i<=m;i++){
if (sum!=n-now+1){
a[i].ans=now;
sum-=a[i].val;
if (sum>=n-now){
now++;
}
else{
now=n-sum+1;
}
}
else{
a[i].ans=now;
sum-=a[i].val;
now+=a[i].val;
}
}
if (now!=n+1)
flag=1;
if (flag){
cout<<"-1"<<endl;
return 0;
}
for (int i=1;i<=m;i++)
cout<<a[i].ans<<" ";
cout<<endl;
return 0;
}
D. Dreamoon Likes Sequences
题意：每次会给你一个整数d和m m是取模的不用管他 计算的时候记得加上就好
那我们看看题意就是我们构造一个严格递增数组a 并且a[n]<=d 那我们可以理解成在1-d里面选数字组成 这个数组 同时我们还在构造一个数组b b1=a1,
b[i]=b[i-1]⊕a[i] 我们这里可以把 b[i]理解成 a1⊕a2⊕…⊕ai 同时这个数组也满足了严格递增的条件。问你a数组的种类数是多少 结果记得取模m
解法：那我们看到这里就知道这题肯定就是跟a数组怎么构造有关 a严格递增没什么好说的 我们就看b （异或 凡是看到这些就直接把数转成二进制然后去思考吧 cf题一般这样都能想出特点） 具体怎么想 我们最好还是看看样例 我们发现d=3的时候
1 2 ，1 3都满足条件 那么他们的数组b满足什么条件呢 我们发现b[i]的数的二进制的最高位一定会比b[i-1]的二进制最高位要高 这说明什么 说明a[i]的二进制最高位一定比a[i-1]的二进制的最高位要大 这也就解释了 为什么d=3的时候 2 3不行 （因为最高位是一样的啊 那我们就可以知道了a[i]的每一个数的最高位都是严格递增就行了 那么想到这里怎么写呢 这里我用到了以前fzh大佬给我讲题的一个思路 我们这么看 我们先假设d=7 那么4 5 6 7的最高位都是第三位 2 3是第二位 1是第一位 数组a的长度又不确定 那么这么想 1 也就是最高位是第一位的这个区间里面 我有两种选择 就是取1 或者不取 那么我们在看2 3这个区间 我有三种选择 不取 取2 取3 那么后面都是以此类推 所以d=7的时候结果是1* 2* 3*5-1。这里减1是因为 你要去掉你已经计算的 全部都不取的可能性 于是就解出来了
ps 记得判断 最后一个区间可能不是完全都能取的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t;
cin>>t;
while (t--){
ll d,m;
scanf("%lld%lld",&d,&m);
ll ans=1,t=1;
while (t<=d){
ans=ans*(min(t,d-t+1)+1)%m;
t<<=1;
}
cout<<(ans+m-1)%m<<endl;
}
return 0;
}
希望对大家有帮助嘻嘻
京公网安备 11010502036488号