首页 > Educational Codeforces Round 54

Educational Codeforces Round 54

这套题不难，但是场上数据水，导致有很多叉点

A.

因为是让求删掉一个后字典序最小，那么当a[i]>a[i+1]的时候，删掉a[i]一定最优！这个题有个叉点，当扫完一遍如果没有满足条件的，就删去最后一个字符。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include <set>
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 
13 using namespace std;
14 const double eps = 1e-6;
15 const int MOD=1e9+7;
16 typedef long long LL;
17 typedef unsigned long long ull;
18 const int INF=2147000000;
19 const LL inf = 1e18;
20 LL gcd(LL a,LL b){
21     if(!b)return a;
22     return gcd(b,a%b);
23 }
24 LL lcm(LL a,LL b){
25     return a/gcd(a,b)*b;
26 }
27 const int maxn=2e5+100;
28 char s[maxn];
29 int n;
30 int main(){
31     scanf("%d",&n);
32     scanf("%s",s);
33     int pos=-1;
34     for(int i=0;i1;i++){
35         if(s[i+1]<s[i]){
36             pos=i;
37             break;
38         }
39     }
40     if(pos==-1)
41         pos=n-1;
42     for(int i=0;i)
43         if(i!=pos)
44             printf("%c",s[i]);
45 return 0;
46 }
View Code

 

B.

当n是偶数的时候一定是每次都减2，也就是n/2.当n奇数的时候，就暴力减质数一直减到是偶数或者为0.注意要特判当前n是不是质数。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include <set>
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 
13 using namespace std;
14 const double eps = 1e-6;
15 const int MOD=1e9+7;
16 typedef long long LL;
17 typedef unsigned long long ull;
18 const int INF=2147000000;
19 const LL inf = 1e18;
20 LL gcd(LL a,LL b){
21     if(!b)return a;
22     return gcd(b,a%b);
23 }
24 LL lcm(LL a,LL b){
25     return a/gcd(a,b)*b;
26 }
27 const int maxn=2e5+100;
28 
29 int prime[maxn];
30 int vis[maxn];
31 int num;
32 int init(int n){
33     int m = (int)sqrt(n);
34     vis[1]=1;
35 
36     for(int i = 2;i<=m;i++){
37         for(int j =i*i; j<=n;j+=i){
38             vis[j]=1;
39         }
40     }
41     for(int i=2;i<=n;i++){
42         if(!vis[i]){
43             num++;
44             prime[num] = i;
45         }
46     }
47     return num;
48 }
49 bool judge(LL x){
50     int m =(int)sqrt(x);
51     for(int i=2;i<=m+1;i++){
52         if(x%i==0)
53             return false;
54     }
55     return true;
56 }
57 LL n;
58 int
59 main(){
60     cin>>n;
61     LL ans=0;
62     init(2e5);
63     if(n%2==0){
64         cout<2<<endl;
65         return 0;
66     }
67     bool ok=1;
68     while(n%2){
69         if(judge(n)){
70             ans+=1;
71             ok=0;
72             break;
73         }
74 
75         int flag=0;
76         for(int i=1;i<=num&&prime[i]<=n;i++){
77             if(n%prime[i]==0){
78            // printf("!!%d
",prime[i]);
79                 flag=prime[i];
80                 break;
81             }
82         }
83         //printf("%d
",flag);
84         if(!flag)flag=n;
85         n-=flag;
86         ans++;
87     }
88     if(ok)
89     ans+=n/2;
90     cout<endl;
91 return 0;
92 }
View Code

 

C.

这个题就是解一个一元二次方程，应该也可以三分来做。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include <set>
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 
13 using namespace std;
14 const double eps = 1e-6;
15 const int MOD=1e9+7;
16 typedef long long LL;
17 typedef unsigned long long ull;
18 const int INF=2147000000;
19 const LL inf = 1e18;
20 LL gcd(LL a,LL b){
21     if(!b)return a;
22     return gcd(b,a%b);
23 }
24 LL lcm(LL a,LL b){
25     return a/gcd(a,b)*b;
26 }
27 int main(){
28     int T;
29     scanf("%d",&T);
30 
31     int d;
32     for(int kas=1;kas<=T;kas++){
33         scanf("%d",&d);
34         double del = d*d - 4*d;
35         if(del<0){
36             printf("N
");
37         }else if(del == 0){
38             double ans=(double)d/2;
39 
40             printf("Y %.9f %.9f
",ans,(double)(d-ans));
41         }else{
42             double ans1 = (double)(d+sqrt(del))/2;
43             if(ans1<=d){
44                 printf("Y %.9f %.9f
",ans1,(double)(d-ans1));
45             }else{
46                 double ans1 = (double)(d-sqrt(del))/2;
47                 if(ans1<0){
48                     printf("N
");
49                 }else
50                     printf("Y %.9f %.9f
",ans1,(double)(d-ans1));
51             }
52         }
53     }
54 return 0;
55 }
View Code

D.

最短路+贪心；我们先跑出最短路树来，如果k大于等于最短路树的边数，则树上的边全留下。否则的话就要删树上的边，删哪些呢？从最远（d[u]最大）的边开始删一定是最优的。

  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include <set>
  6 #include 
  7 #include 
  8 #include 
  9 #include 
 10 #include 
 11 #include 
 12 
 13 using namespace std;
 14 const double eps = 1e-6;
 15 const int MOD=1e9+7;
 16 typedef long long LL;
 17 typedef unsigned long long ull;
 18 const int INF=2147000000;
 19 const LL inf = 1e18;
 20 LL gcd(LL a,LL b){
 21     if(!b)return a;
 22     return gcd(b,a%b);
 23 }
 24 LL lcm(LL a,LL b){
 25     return a/gcd(a,b)*b;
 26 }
 27 const int maxn=3e5+100;
 28 int head[maxn],to[2*maxn],Next[2*maxn],w[2*maxn],id[2*maxn];
 29 struct Edge{
 30     int from,to,w,id;
 31 };
 32 vectoredges;
 33 int sz,n,m,k;
 34 void init(){
 35     sz=0;
 36     memset(head,-1,sizeof(head));
 37 }
 38 void add_edge(int a,int b,int c,int d){
 39     ++sz;
 40     to[sz]=b;
 41     w[sz]=c;
 42     id[sz]=d;
 43     Next[sz]=head[a];
 44     head[a]=sz;
 45 }
 46 struct HeapNode{
 47     int u;
 48     LL d;
 49     int from;
 50     bool operator <(const HeapNode& rhs)const{
 51         return d>rhs.d;
 52     }
 53 };
 54 int done[maxn],p[maxn];
 55 LL d[maxn];
 56 
 57 Edge edge[maxn];
 58 
 59 priority_queueq;
 60 void dij(){
 61     q.push((HeapNode){ 1,0,-1});
 62     for(int i=0;i<=n;i++)
 63         d[i]=inf;
 64     while(!q.empty()){
 65         HeapNode x= q.top();q.pop();
 66         if(done[x.u])
 67             continue;
 68         done[x.u]=1;
 69         d[x.u] = x.d;
 70         p[x.u] = x.from;
 71         //printf("%d
",x.from);
 72         for(int i=head[x.u];i!=-1;i=Next[i]){
 73             int v = to[i];
 74             if(d[v]>d[x.u]+w[i]){
 75                 q.push((HeapNode){v,d[x.u]+w[i],id[i]});
 76             }
 77         }
 78     }
 79 }
 80 
 81 struct Node{
 82     int u;
 83     LL d;
 84     int from;
 85     bool operator <(const Node &rhs)const{
 86         return d<rhs.d;
 87     }
 88 };
 89 int vis[maxn];
 90 
 91 priority_queueQ;
 92 
 93 int main(){
 94     scanf("%d%d%d",&n,&m,&k);
 95 
 96     init();
 97     for(int i=1;i<=m;i++){
 98         int a,b,c;
 99         scanf("%d%d%d",&a,&b,&c);
100         add_edge(a,b,c,i);
101         add_edge(b,a,c,i);
102         edge[i]=(Edge){a,b,c,i};
103     }
104     dij();
105     for(int i=1;i<=n;i++){
106         //printf("@%d
",p[i]);
107         if(p[i]!=-1&& !vis[p[i]]){
108             edges.push_back(edge[p[i]]);
109             vis[p[i]]=1;
110             Q.push((Node){i,d[i],p[i]});
111            // printf("!!!%d %d %d %d
",edge[p[i]].from,edge[p[i]].to,edge[p[i]].w,p[i]);
112         }
113     }
114     if(edges.size()<=k){
115         printf("%d
",edges.size());
116         for(int i=0;i){
117             printf("%d ",edges[i].id);
118         }
119     }else{
120         int num = edges.size();
121         while(num>k&&!Q.empty()){
122             Q.pop();
123             num--;
124         }
125         printf("%d
",k);
126         while(!Q.empty()){
127             printf("%d ",Q.top().from);
128             Q.pop();
129         }
130     }
131 return 0;
132 }
View Code

E.

树状数组或者线段树维护一下。因为每个点的值只可能是来自于它的祖先结点，所以跑dfs的时候，进入这个点的时候更新树状数组，退栈的时候还原树状数组

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 
 7 using namespace std;
 8 const int maxn=3e5+100;
 9 typedef long long LL;
10 int head[maxn],to[2*maxn],Next[2*maxn];
11 int n,sz,m;
12 void add_edge(int a,int b){
13     sz++;
14     to[sz]=b;Next[sz]=head[a];head[a]=sz;
15 }
16 int lowbit(int x){
17     return x&(-x);
18 }
19 LL sumv[maxn];
20 void update(int x,int v){
21     while(x<=n){
22         sumv[x]+=v;
23         x+=lowbit(x);
24     }
25 }
26 LL query(int x){
27     LL res=0;
28     while(x){
29         res+=sumv[x];
30         x-=lowbit(x);
31     }
32     return res;
33 }
34 struct Node{
35     int d,x;
36 };
37 vectorV[maxn];
38 int fa[maxn],dep[maxn];
39 LL ans[maxn];
40 
41 void dfs(int u,int Fa,int depth){
42     fa[u]=Fa;
43     dep[u]=depth;
44     for(int i=0;i){
45         Node N = V[u][i];
46         update(min(N.d+depth,n),N.x);
47     }
48     ans[u] = query(n)-query(depth-1);
49     for(int i=head[u];i!=-1;i=Next[i]){
50         int v=to[i];
51         if(v==Fa)continue;
52         dfs(v,u,depth+1);
53     }
54     for(int i=0;i){
55         Node N = V[u][i];
56         update(min(N.d+depth,n),-N.x);
57     }
58 }
59 
60 int main(){
61     scanf("%d",&n);
62     memset(head,-1,sizeof(head));
63     for(int i=1;i){
64         int a,b;
65         scanf("%d%d",&a,&b);
66         add_edge(a,b);
67         add_edge(b,a);
68     }
69     scanf("%d",&m);
70     for(int i=1;i<=m;i++){
71         int v,d,x;
72         scanf("%d%d%d",&v,&d,&x);
73         V[v].push_back((Node){d,x});
74     }
75     dfs(1,-1,1);
76     for(int i=1;i<=n;i++){
77         printf("%I64d ",ans[i]);
78     }
79 return 0;
80 }
View Code

F.

贪心+分类讨论。

每一页多的为Max，少的为Min。那么一定是用少的将多的分隔开。所以如果大小关系不同则不会产生影响。否则的话，这一页我们要它最左边多出来的那块尽量长。lef=k-lastR;那么Max=Max-lef,Min=Min-1;然后我们分类讨论：

1.ceil(Max/k)-1>Min 则return false;

2.ceil(Max/k)<=Min

则说明右边不会剩下。则lastR=0。

3.ceil(Max/k)==Min-1的话，恰好被分割开，右边会有剩余，但是剩余的长度<=k，属于合法。

lastR= Max%k ==0?k:Max%k

这个也有叉点，要主要Min==Max的情况

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 
 8 using namespace std;
 9 const int maxn = 3e5 + 100;
10 int n, k;
11 int x[maxn][2];//0 x,1 y
12 int state,laststate,lastR;
13 int main(){
14     scanf("%d%d", &n, &k);
15     for(int i = 1; i <= n; i++){
16         scanf("%d", &x[i][0]);
17     }
18     for(int i = 1; i <= n; i++){
19         scanf("%d", &x[i][1]);
20     }
21     bool flag = 1;
22     for(int i = 1; i <= n; i++){ //x >= y state = 1;else state = 0;
23         int Min = min(x[i][0], x[i][1]);
24         int Max = max(x[i][0], x[i][1]);
25        // printf("%d %d
",Min,Max);
26         if(x[i][0] > x[i][1])
27             state = 1;
28         else if(x[i][0] < x[i][1])
29             state = 0;
30         else state = -1;
31         if(state == laststate||laststate == -1||state == -1){
32             int lef = k - lastR;
33             Max = Max - lef;
34             Min = Min - 1;
35         }
36         //printf("%d %d
",(int)ceil((double)Max/k),Min);
37 
38         if((int)ceil((double)Max/k)-1 > Min){
39             flag = 0;
40             break;
41         }else if((int)ceil((double)Max/k) <= Min){
42             lastR = 0;
43         }else{
44             lastR = Max%k == 0?k:Max%k;
45         }
46         laststate = state;
47     }
48     if(!flag){
49         printf("NO
");
50     }else{
51         printf("YES
");
52     }
53 return 0;
54 }
View Code

G.

好像是打反转标记的线段树，留坑

 

转载于:https://www.cnblogs.com/LQLlulu/p/9955849.html

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • PCL点云分割（2）

    关于点云的分割算是我想做的机械臂抓取中十分重要的俄一部分，所以首先学习如果使用点云库处理我用kinect获取的点云的数据，本例程也是我自己慢慢修改程序并结合官方API 的解说实现的，其中有很多细节如果直接更改源程序，可能会因为数据类型，或者头文件等各种原因编译不过，会导致我们比较难得找出其中的错误，首先我们看一下我自己设定的一个场景，...

  • PCL点云配准（2）

    /* 使用正态分布变换进行配准的实验 。其中room_scan1.pcd room_scan2.pcd这些点云包含同一房间360不同视角的扫描数据 */ #include #include #include #include

  • PCL点云变换与移除NaN

    #include #include #include #include ...

  • PCL滤波介绍(3)

    #include #include #include #include #include #include...

  • PCL滤波介绍（2）

    #include #include #include #include int main (int argc,...

  • L1-056 猜数字 (结构体解决)

    L1-056 猜数字 (20 分) 一群人坐在一起，每人猜一个 100 以内的数，谁的数字最接近大家平均数的一半就赢。本题就要求你找出其中的赢家。 输入格式： 输入在第一行给出一个正整数N（≤104）。随后 N 行，每行给出一个玩家的名字（由不超过8个英文字母组成的字符串）和其猜的正整数（≤ 100）。 输出格式： 在一行中...

  • [NOIP模拟测试9]题(Problem) 题解 (组合数全家桶+dp)

    达哥送分给我我都不要，感觉自己挺牛批。 $type=0:$ 跟visit那题类似，枚举横向移动的步数直接推公式： $ans=sum C_n^i imes C_i^{frac{i}{2}} imes C_{n-i}^{frac{n-i}{2}},i\% 2=0$ $type=1:$ 因为不能触碰负半轴，所以可以把右移看成...

  • Codeforces Round #447 (Div. 2) B. Ralph And His Magic Field 数学

    题目链接 题意：给你三个数n,m,k;让你构造出一个nm的矩阵，矩阵元素只有两个值（1，-1),且满足每行每列的乘积为k，问你多少个矩阵。 解法：首先，如果n，m奇偶不同，且k=-1时，必然无解： 设n为奇数，m为偶数，且首先要满足每行乘积为-1，那么每行必然有奇数个-1，那么必然会存在有偶数个-1.。满足每列乘积为-1，那么每列必...

  • 4514: [Sdoi2016]数字配对

    Description 有 n 种数字，第 i 种数字是 ai、有 bi 个，权值是 ci。 若两个数字 ai、aj 满足，ai 是 aj 的倍数，且 ai/aj 是一个质数， 那么这两个数字可以配对，并获得 ci×cj 的价值。 一个数字只能参与一次配对，可以不参与配对。 在获得的价值总和不小于 0 的前提下，求最多进行多少次配对...

  • 快速幂 + 矩阵快速幂

    快速幂       1 #include 2 #include 3 #include 4 #define LL long long 5 using namespace std; 6 7 LL Pow(LL a, LL b) 8 { 9 LL an...

©2024 11GX.COM