「题解」水题集

这篇博客专门拿来存放一些简单题的题解，水洛谷题解用的，右上角可以快速定位题目，还是希望能对大家有些帮助（指找到了一堆水题）
本博客持续更新中…

CF1407A Ahaha

洛谷原题面

• 题意理解

  输入T组数据。使得一个长度为 $n$ 由 $0$ 和 $1$ 组成的数组删除 $m$ 个数后，奇数下标的数字之和等于偶数下标的数字之和。 $(0\leq m\leq \cfrac{n}{2})$

  输出剩下的数组长度 $k$ 和剩下的所有数字。 $( \cfrac{n}{2} \leq k\leq n)$

• 思路

  设 $0$ 的数量为 $x$ ，$1$ 的数量为 $y$ 。既然这个数组只由 $0$ 和 $1$ 组成，那么要么是 $x<\cfrac{n}{2}<y$ ，要么是 $y\leq \cfrac{n}{2}\leq x$

  所以当 $y\leq x$ 时，我们直接把所有的 $1$ 全部删掉，剩下的数全部为 $0$ ，显然满足条件；当 $x<y$ 时，直接把所有的 $0$ 删掉，此时 $k$ 必须为偶数，不为偶数再删去一个 $1$ 即可

• 代码实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

  #include<bits/stdc++.h> using namespace std; const int N=1e3+9; int T,n,x,one,zer;//one是1的数量,zer是2的数量 int main(){ scanf("%d",&T); while(T--){ one=zer=0; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&x); if(x==0) zer++; else one++; } if(one>zer){ if((n-zer)%2!=0) n--; printf("%d\n",n-zer); for(int i=1;i<=n-zer;i++) printf("1 "); putchar('\n'); } else{ printf("%d\n",n-one); for(int i=1;i<=n-one;i++) printf("0 "); putchar('\n'); } } return 0; }

P1834 速算问题

洛谷原题面

• 题意

  给定4个1~9的整数，通过括号和加、减、乘、除使结果为24，过程中不允许出现分数。输出时需要将每一步运算的括号补齐，并输出字典序最小的一个

• 思路

  不知道其他题解怎么写这么多
  四个数，三个填入运算符的位置，四个运算符，甚至可以直接全排列，现在问题就在字典序上面了。通过查阅 ASCII 码，我们知道字典序优先级为 ( , ) , * , + , - , / , 1 ~ 9 。同时对于确定位置的四个数 $a,b,c,d$ ，很明显有以下三种运算顺序

  $(((a\ \ b)\ \ c)\ \ d)\\ ((a\ \ b)\ \ (c\ \ d))\\ (a\ \ (b\ \ (c\ \ d)))$

  全排列时，第三种情况等同于第一种情况。

  于是我们可以先对四个数字排序，然后对于每个填入运算符的位置，按字典序枚举四个运算符。那么我们是否可以在第一种运算顺序成立时输出结果，第一种运算顺序无解时输出第二次运算顺序的第一个解呢？

  请看这两个式子 $(((2*6)+4)+8)$ 与 $(((2*6)*8)/4)$ ，很明显后者的 ‘*’ 字典序在前所以后者才是正解，但全排列时应该是前者优先。因此，我们需要把每一个解的字符串存下来，排序后再输出。

• 代码实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

  #include<bits/stdc++.h> using namespace std; const int M=114514; int a[5],ans,x,y,z,xx,yy,zz,cnt;//x,y,z为第一种运算顺序，xx,yy,zz是第二种 char op[5]={' ','*','+','-','/'},str[20]; string s[M]; int operate(int a,int b,char c){//整数a,b,运算符 if(c=='+') return a+b; else if(c=='-') return a-b; else if(c=='*') return a*b; else{ if(b==0||a%b!=0) return M;//这样就不用对非法解再处理了 return a/b; } } int main(){ for(int i=1;i<=4;i++) scanf("%d",&a[i]); sort(a+1,a+5); do{ for(int i=1;i<=4;i++){ xx=x=operate(a[1],a[2],op[i]); for(int j=1;j<=4;j++){ y=operate(x,a[3],op[j]); for(int k=1;k<=4;k++){ z=operate(y,a[4],op[k]); if(z==24){ //sprintf转化输出内容到char[] sprintf(str,"(((%d%c%d)%c%d)%c%d)",a[1],op[i],a[2],op[j],a[3],op[k],a[4]); s[++cnt]=str; } yy=operate(a[3],a[4],op[k]); zz=operate(xx,yy,op[j]); if(zz==24){ sprintf(str,"((%d%c%d)%c(%d%c%d))",a[1],op[i],a[2],op[j],a[3],op[k],a[4]); s[++cnt]=str; } } } } }while(next_permutation(a+1,a+5));//全排列小技巧 sort(s+1,s+1+cnt); printf("%s",s[1].c_str());//string转char[] return 0; }

CF1407B Big Vova

洛谷题面
CF原题面

• 题意

  有 $T$ 组数据。对于每组数据，有一个长度为 $n$ 的序列 $a$ ，需要对 $a$ 重新排列得到序列 $b$ 并输出。设 $c_i=\gcd(b_1,b_1\cdots b_n)$ ，你重排后得到的数组 $b$ ,需要满足对应计算出的数组 $c$ 的字典序最大。

  数据范围：$T\leq 10^3，n\leq 10^3，1\leq a\leq 10^3$ ，其中所有数据中 $n$ 的和不超过 $10^3$

• 思路

  首先我们先想想怎么解决 $c$ 数组的计算，很明显可以推出 $c_1=b_1 ，c_{i+1}=\gcd(c_i,b_{i+1})$ ，有点类似于前缀和的思想。

  然后我们再思考如何做到字典序最大。根据字典序的判定，我们可以知道 $b_1$ 肯定是原数组 $a$ 中最大的数。然后我们再看下一个数，明显需要在 $a$ 中选出一个使 $c_2=\gcd(c_1,b_2)$ 最大的数。以此类推，贪心的思维就体现出来了。

  我们在每次选数时枚举一遍 $a_i$ ，时间复杂度为 $O(n^2)$ ，那么最终的时间复杂度就是 $O(Tn^2)$ ，翻译中给的数据明显无法直接这样暴力。但阅读原题面就会发现翻译没有给全，所有数据中的 $n$ 之和不超过 $10^3$ 。于是我们就可以放心大胆打暴力了！

  It is guaranteed that the sum of n over all test cases does not exceed 10^3

• 代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

  #include<bits/stdc++.h> using namespace std; const int N=1e3+9; int T,n,a[N],maxx,x,c; bool use[N];//记录用过的数 int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); } int main(){ scanf("%d",&T); while(T--){ memset(use,0,sizeof(use)); maxx=c=0; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(maxx<a[i]) maxx=a[i],c=i;//用c记录下标,maxx记录最大数 } use[c]=1;x=c=a[c]; printf("%d ",maxx); for(int i=1;i<n;i++){ maxx=0; for(int j=1;j<=n;j++){ if(!use[j]){ int d=gcd(c,a[j]); if(d>maxx) maxx=d,x=j;//x来记录下标 } } c=maxx,use[x]=1; printf("%d ",a[x]); } puts(""); } return 0; }

CF1712C Sort Zero

洛谷题面
CF原题面

• 题意

  有 $T$ 组数据，每组数据给出一个正整数 $n$ 和 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$ ，这 $n$ 个正整数形成一个 $1$ 到 $n$ 的排列。你可以任意把其中一个正整数 $x$ 变为 $0$。求数组 $a$ 变为不降序列的最小操作次数。

  数据范围：$1\leq T\leq 10^4 ,1\leq n\leq 10^5 ,1\leq a_i\leq n$

• 思路

  因为要满足 $\forall i,a_{i-1}\leq a_i$，所以出现 $a_{i-1}>a_i$ 时，需要把 $a_{i-1}$ 变为 $0$，而在 $a_{i-1}$ 以前的数也会因此变为 $0$。我们只需要维护一个不下降的序列，每当出现一个数 $x$ 小于序列中最后一个数，就把序列中所有数变为 $0$，标记一下变为 $0$ 的数，排空序列防止重复遍历，最后加入 $x$。最后从 $1$ 到 $n$ 遍历，统计被标记数的个数。这样保证时间复杂度为 $O(Tn)$

• 代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

  #include<bits/stdc++.h> using namespace std; const int N=1e5+9; int T,n,a[N]; bool vis[N];//记录变为0的数 int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); int tot=0,x,ans=0; for(int i=1;i<=n;i++){ scanf("%d",&x); if(vis[x]) x=0;//之前变为0的数，在读入时直接修改为0 if(tot>0&&a[tot]>x){ while(tot>0){ vis[a[tot]]=1; tot--; } } a[++tot]=x; } for(int i=1;i<=n;i++){ if(vis[i]) ans++;//统计答案 } printf("%d\n",ans); for(int i=0;i<=n;i++) a[i]=vis[i]=0; } return 0; }

CF1737B Ela’s Fitness and the Luxury Number

洛谷题面
CF题面

• 题意

  有 $T$ 组数据。每组数据给出两个正整数 $l,r$，求出

  $\sum_{x\in[l,r],x\in \mathbb{Z}}{[\lfloor\sqrt x\rfloor\mid x]}$

  数据范围：$1\leq T\leq 10^4,1\leq l\leq r\leq 10^{16}$

• 思路

  这种题只需要求出 $[1,r]$ 与 $[1,l-1]$ 中满足情况的差值，也就是说，我们只需要知道如何求 $[1,x],x\in\mathbb{Z}$ 中满足条件的数。

  首先我们可以想，若设正整数 $x$，那么对于所有正整数 $y\in [x^2,(x+1)^2)$，满足 $\lfloor\sqrt y\rfloor=x$。那么我们只需要知道 $[x^2,(x+1)^2)$ 中有几个数能被 $x$ 整除，可以通过求这个区间的大小。也就是

  $(x+1)^2-x^2=2x+1$

  然后再加上 $x^2$ 的情况，也就是说在 $[x^2,(x+1)^2)$ 中，有 $3$ 个数可以被 $x$ 整除。这题到这里基本就结束了。

• 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int T;
ll l,r;

int main(){
    cin>>T;
    while(T--){
        scanf("%lld%lld",&l,&r);
        l--;
        ll x=sqrt(l),y=sqrt(r),sl,sr;
        sl=3*(x-1)+1,sr=3*(y-1)+1;
        if(x*x!=l) sl+=((l-x*x)/x);
        if(y*y!=r) sr+=((r-y*y)/y);
        if(l==0) sl=0;//特判一下
        printf("%lld\n",sr-sl);
    }
    return 0;
}

CF1743C Save the Magazines

洛谷题面
CF题面

• 思路

  应该是道贪心题？赛时想到的是动态规划。$f_{i,0/1}$ 表示第 $i$ 个箱子，$0$ 表示不移动板子，$1$ 表示移动板子时最多能保留多少报纸。

  显然，当第 $i$ 个箱子上无板子时，有 $f_{i,0}=max(f_{i-1,1},f_{i-1,0})$

  当第 $i$ 个箱子上有板子时，可以选择是否移动这个板子，不移动则有 $f_{i,0}=max(f_{i-1,1},f_{i-1,0})+a_i$

  若第 $i-1$ 没有板子则可以直接移动，有 $f_{i,1}=f_{i-1,0}+a_{i-1}$

  反之需要先移动第 $i-1$ 个板子，有 $f_{i,1}=f_{i-1,1}+a_{i-1}$

• 代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

  #include<bits/stdc++.h> using namespace std; const int N=2e5+9; int n,T,a[N],f[N][2]; char s[N]; int main(){ scanf("%d",&T); while(T--){ scanf("%d%s",&n,s+1); for(int i=1;i<=n;i++) scanf("%d",&a[i]); f[1][0]=f[1][1]=0; if(s[1]=='1') f[1][0]=a[1];//初始化 for(int i=2;i<=n;i++){ if(s[i]=='0') f[i][0]=max(f[i-1][0],f[i-1][1]),f[i][1]=0; else{ f[i][0]=max(f[i-1][0],f[i-1][1])+a[i]; if(s[i-1]=='0') f[i][1]=f[i-1][0]+a[i-1]; else f[i][1]=f[i-1][1]+a[i-1]; } } printf("%d\n",max(f[n][1],f[n][0])); } return 0; }