ACM团队周赛题解(2)

Wesley13
• 阅读 522

拉了CF583和CF486的两套div2题目

还是先贴宏定义部分

#define MAXN 1000000+5
#define MOD 1000000007
#define PI (acos(-1.0))
#define EPS 1e-6
#define MMT(s,a) memset(s, a, sizeof s)
#define GO(i,a,b) for(int i = (a); i < (b); ++i)
#define GOE(i,a,b) for(int i = (a); i <= (b); ++i)
#define OG(i,a,b) for(int i = (a); i > (b); --i)
#define OGE(i,a,b) for(int i = (a); i >= (b); --i)


A - Asphalting Roads(CF-583A)

题意就是n条水平路,n条竖直路,构成井字形状。然后第i天会到(xi,yi)这个路口,如果这个路口得两条路都没有被染色,就输出这天并把两个路口都染上颜色,否则跳到下一天。

输出所有可以染色得天数。

题目思路:标记遍历即可

 1 int main(){
 2     ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
 3     int n,x,y;
 4     cin>>n;
 5     int mp1[55] = {0},mp2[55] = {0};
 6     GO(i,0,n*n){
 7         cin>>x>>y;
 8         if(mp1[x] == 0 && mp2[y] == 0){
 9             cout << i+1 << " ";
10             mp1[x] = mp2[y] = 1;
11         }
12     }
13     cout << endl;
14 
15     return 0;
16 }

B - Robot's Task(CF-583B)

题意就是最开始从左往右走,如果现在值Num比a[i]大,则Num+1,否则跳过他,走到尽头如果有数没有经过,则转向再次走,已经走过的地方不能再走。

Num初始值为0,问至少转向几次。

思路:模拟即可

 1 int main(){
 2     ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
 3     int n;
 4     int a[1005] = {0},vis[1005] = {0};
 5     cin>>n;
 6     GOE(i,1,n){
 7         cin>>a[i];
 8     }
 9     bool flag = true;
10     int cnt = n,ans = 0,num = 0;
11     while(cnt > 0){
12         if(flag){
13             GOE(i,1,n){
14                 if(!vis[i] && num >= a[i]){
15                     vis[i] = 1;
16                     num++;
17                     cnt--;
18                 }
19             }
20         }
21         else{
22             OGE(i,n,1){
23                 if(!vis[i] && num >= a[i]){
24                     vis[i] = 1;
25                     num++;
26                     cnt--;
27                 }
28             }
29         }
30         flag = !flag;
31         if(cnt > 0)
32             ans++;
33     }
34     cout << ans << endl;
35 
36     return 0;
37 }

C - GCD Table(CF-583C)

给你一个打乱了的GCD表,问是哪些值构成的。

思路:这n个数一定就是对角线上的数,直接降序排列然后暴力找,每次找到的最大的数一定是其中一个数,然后求出它与已经求出的所有数的gcd在队列中去掉两个这个gcd数,保证所有大于等于下一个数字的gcd一定都被去掉了,剩下的最大的又是要找的数。

额外定义

template
using maxHeap = priority_queue<T, vector, less >;

template
inline T gcd(T a, T b){ return b==0 ? a : gcd(b,a%b); }

代码

 1 int main(){
 2     ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
 3     int n,k = 0,temp,num;
 4     int a[250050],b[250050];
 5     cin>>n;
 6     GOE(i,1,n*n){
 7         cin>>a[i];
 8     }
 9     sort(a+1,a+1+n*n);
10     maxHeap<int> q;
11     OG(i,n*n,0){
12         if(!q.empty())
13             temp = q.top();
14         else
15             temp = 0;
16         if(a[i] == temp){
17             q.pop();
18             continue;
19         }
20         GO(j,0,k){
21             num = gcd(b[j],a[i]);
22             q.push(num);
23             q.push(num);
24         }
25         b[k++] = a[i];
26     }
27     GO(i,0,k)
28         cout << b[i] << " ";
29     cout << endl;
30     
31     return 0;
32 }

F - Calculating Function(CF-486A)

题意就是按照他给的公式输出F(n);

思路:可以推出n为偶数是F(n) = n/2,否则F(n) = n/2 - n;

代码

 1 int main(){
 2     ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
 3     ll n;
 4     cin>>n;
 5     if (n&1)
 6         cout << n/2 - n << endl;
 7     else
 8         cout << n/2 << endl;
 9 
10     return 0;
11 }

G - OR in Matrix(CF-486B)

题目就是说bij为i行和j列的值OR操作的结果,现在给你操作后的表,要你求操作前的表。

思路:如果bij = 0,则证明i行和j列全是0,如果是1,则证明i行和j列必须有一个1,所以先把所有值设为1,按照题目把某些行列变为0,再判断一遍是否满足题意即可

代码

 1 int main(){
 2     ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
 3     int n,m;
 4     int a[105][105],b[105][105];
 5     fill(b[0],b[0]+105*105,1);
 6     cin>>n>>m;
 7     GOE(i,1,n){
 8         GOE(j,1,m){
 9             cin>>a[i][j];
10             if(a[i][j] == 0){
11                 GOE(ii,1,n)
12                     b[ii][j] = 0;
13                 GOE(jj,1,m)
14                     b[i][jj] = 0;
15             }
16         }
17     }
18 
19     GOE(i,1,n){
20         GOE(j,1,m){
21             if(a[i][j] == 1){
22                 int flag = 0;
23                 GOE(ii,1,n){
24                     if(b[ii][j] == 1){
25                         flag = 1;
26                         break;
27                     }
28                 }
29                 GOE(jj,1,m){
30                     if(b[i][jj] == 1){
31                         flag = 1;
32                         break;
33                     }
34                 }
35                 if(!flag){
36                     cout << "NO" << endl;
37                     exit(0);
38                 }
39             }
40         }
41     }
42 
43     cout << "YES" << endl;
44     GOE(i,1,n){
45         GOE(j,1,m)
46             cout << b[i][j] << " ";
47         cout << endl;
48     }
49 
50     return 0;
51 }

H - Palindrome Transformation(CF-486C)

题意就是4种操作,最开始在k位置操作,问最少操作多少次使得原串变成回文串。

思路:因为是对称的,我们先不要管最开始在哪个位置,遍历即可,当a[i] != a[n-i-1]时候,我们再想是变a[i]还是变另一个,然后答案加上这个值。同时往容器中加上从k走到i远还是走到n-i-1近。

最后排序,答案加上最远距离于最近距离之差再加上这两者距离k最近的距离即可。

为什么只需要不需要管k的位置,因为k无论在哪里,我们都需要把所有不符合的字符走到,所以这里得花掉最远距离和最近距离的差,同时我们最开始在k,需要走到最近的位置开始遍历上一段距离,所以最终答案就是

ans = 每个不合格字符的操作次数 + 不合格字符的区间长度 + 从k位置走到这个区间的某一端点的距离;

因为不管你的k是否在这个区间内,都需要遍历一遍这个区间。

 1 int main(){
 2     ios_base::sync_with_stdio(false), cout.tie(0), cin.tie(0);
 3     int n,k;
 4     string s;
 5     vector<int> q;
 6     cin>>n>>k>>s;
 7     int len = n/2,ans = 0;
 8     GO(i,0,len){
 9         if(s[i] != s[n-1-i]){
10             int tp = abs(s[i] - s[n-1-i]);
11             tp = min(tp,26-tp);
12             ans += tp;
13             if(tp)
14                 q.PB((abs(i+1-k) < abs(n-i-k)) ? i+1 : n-i);
15         }
16     }
17     int cnt = q.size();
18     if(q.empty())
19         cout << ans << endl;
20     else{
21         sort(q.begin(),q.end());
22         ans += q[cnt-1] - q[0] + min(abs(q[cnt-1]-k),abs(q[0]-k));
23         cout << ans << endl;
24     }
25     return 0;
26 }

D题E题时间关系暂时不补了。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Wesley13 Wesley13
2年前
Java获得今日零时零分零秒的时间(Date型)
publicDatezeroTime()throwsParseException{    DatetimenewDate();    SimpleDateFormatsimpnewSimpleDateFormat("yyyyMMdd00:00:00");    SimpleDateFormatsimp2newS
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Stella981 Stella981
2年前
Docker 部署SpringBoot项目不香吗?
  公众号改版后文章乱序推荐,希望你可以点击上方“Java进阶架构师”,点击右上角,将我们设为★“星标”!这样才不会错过每日进阶架构文章呀。  !(http://dingyue.ws.126.net/2020/0920/b00fbfc7j00qgy5xy002kd200qo00hsg00it00cj.jpg)  2
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
2个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这