CF598: div3解题报告

时间:2022-02-16 23:03:54

CF598:div3解题报告

A: Payment Without Change

思路:
  • 按题意模拟即可。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll T;
cin >> T;
while(T--)
{
ll a, b, n, s;
cin >> a >> b >> n >> s;
if(a*n + b < s) puts("NO");
else
{
if(s - n*a >= 0)
{
s -= n * a;
if(s > b) puts("NO");
else puts("YES");
}
else if(s - n*a < 0)
{
s = s % n;
if(s > b) puts("NO");
else puts("YES");
}
}
}
return 0;
}

B: Minimize the Permutation

思路:
  • 从后往前扫,遇到能往左边挪的就往左边挪。
  • 当然还有位置没有挪过,那就把没有被挪过的地方记录下来,然后再贪心把小的往左边挪。
代码:
#include<bits/stdc++.h>

using namespace std;
const int maxn = 100 + 10;
int a[maxn];
int vis[maxn];
int n;
int main()
{
int T; cin >> T;
while(T--)
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
vis[i] = 0;
}
for(int i = n - 1; i >= 1; i--)
{
if(a[i] > a[i+1])
{
swap(a[i], a[i+1]);
vis[i] = 1;
}
}
for(int i = 1; i <= n - 1; i++)
{
if(vis[i] == 0)
{
if(a[i] > a[i+1])
swap(a[i], a[i+1]);
}
}
for(int i = 1; i <= n; i++)
printf("%d ", a[i]); puts(""); }
return 0;
}

C: Platforms Jumping

思路:
  • 贪心。
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int c[maxn];
int p[maxn];
int a[maxn];
int n, m, d; int main()
{
cin >> n >> m >> d;
int sum = 0;
for(int i = 1; i <= m; i++)
{
scanf("%d", &c[i]);
sum += c[i];
} int cur = 0; //当前的位置
int right = n + 1 - sum;
for(int i = 1; i <= m; i++)
{
p[i] = right;
right += c[i];
} right = n + 1 - sum;
for(int i = 1; i <= m; i++) //考虑每一块木板
{
if(cur + d < right) //跳不过去
{
p[i] = cur + d; //尽可能的贪心把木板放远一点
cur = cur + d + c[i] - 1;
right += c[i];
}
else //能跳过去
{
cur = n + 1;
break;
}
} //最后一步还能跳
cur += d; if(cur <= n) puts("NO");
else
{
puts("YES");
for(int i = 1; i <= m; i++)
for(int j = p[i]; j <= p[i]+c[i]-1; j++)
a[j] = i;
for(int i = 1; i <= n; i++)
printf("%d ", a[i]);
}
return 0;
}

D: Binary String Minimizing

思路:
  • 这题和B是一道题,贪心往左挪,但是有了限制,需要多注意一下。
  • 具体看代码。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
char s[maxn];
ll n, T, k; int main()
{
cin >> T;
while(T--)
{
cin >> n >> k;
scanf("%s", s+1);
int cnt = 1;
for(int i = 1; i <= n; i++)
{
if(s[i] == '0' && k >= i - cnt)
{
swap(s[i], s[cnt]);
k -= i - cnt;
cnt++;
}
else if(s[i] == '0' && k < i - cnt && k != 0)
{
for(int j = i - k; j <= i; j++)
if(s[j] == '1') swap(s[j], s[i]);
k = 0;
}
if(k == 0) break;
}
puts(s+1);
}
return 0;
}

E: Yet Another Division Into Teams

题意描述:
  • 给定\(n\)个学生,每个学生有一个能力值\(a_i\),你的任务是把这些学生划分到若干个集合当中,且每个集合至少三个学生。
  • 对于每一个集合有一个差值定义为学生的能力的最大值减去最小值。
  • 问怎样划分集合可以使得差值最小。
  • 你需要输出最小差值和答案。
  • 数据范围\(3\leq n\leq2*10^5,1\leq a_i\leq10^9\)。
思路:
  • 首先把学生的能力值排个序。
  • 首先我们不需要考虑容量大于\(5\)的集合,因为我们一定可以找到更小的拆分使得结果更小。
  • 又因为我们要求集合至少有三个学生,那么每个集合也就\(3-5\)个人。
  • 设\(f(i)\)表示遍历到了第\(i\)个学生的最小答案。
  • 初态\(f(0)=0,f(i)=+\infty\)。
  • 通过上面的分析,有状态转移方程。
    • \(f(i+3)=min(f(i+3),f(i)+a_{i+2}-a_i)\)
    • \(f(i+4)=min(f(i+4),f(i)+a_{i+3}-a_i)\)
    • \(f(i+5)=min(f(i+5),f(i)+a_{i+4}-a_i)\)
  • 终态为\(f(n)\)。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f; struct Node{
int val;
int idx;
}a[maxn]; bool cmp(Node a, Node b){
return a.val < b.val;
} int n, f[maxn];
int p[maxn];
int t[maxn]; int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i].val);
a[i].idx = i;
} sort(a, a+n, cmp); memset(f, 0x3f, sizeof f);
f[0] = 0; for(int i = 0; i < n; i++)
{
for(int j = 3, delta; j <= 5 && i+j <= n; j++)
{
delta = a[i+j-1].val - a[i].val;
if(f[i+j] > f[i] + delta)
{
p[i+j] = i;
f[i+j] = f[i]+delta;
}
}
} int cur = n;
int cnt = 1; while(cur != 0)
{
//因为sort过所以一定是连续的
for(int i = cur - 1; i >= p[cur]; i--)
t[a[i].idx] = cnt;
cnt++;
cur = p[cur];
} cout << f[n] << " " << cnt - 1 << endl;
for(int i = 0; i < n; i++)
printf("%d ", t[i]); puts("");
return 0;
}

F: Equalizing Two Strings

题意描述:
  • 给你两个字符串\(s\)和\(t\)长度均为\(n\),且只包含小写字母。
  • 每次操作你可以选取长度为\(len\)的序列进行如下操作。
    • 对\(s,t\)的长度为\(len\)子串进行倒序操作。
  • 给你两个串问是否可以通过上述操作变成相等的串。
思路:
  • 对于两个字符串相等的首要条件是:两个字符串中每个字符出现的次数应该相同。
  • 假定现在两个字符串中出现的每个字符次数都相同了。
  • 那么如果某个字符出现两次,那么他们也可以相等。
  • 因为假设说这个出现两次的字符出现在第一个字符串,我先进行一些操作将两个相同的挨在一起(不用考虑第二个字符串如何操作)。
  • 操作完成后,对于第二个字符串,我可以交换两项,同时交换第一个字符串的相同的那两个,那么一定会得到两个字符串相等。
  • 那当我没有相同的字母怎么办?
  • 如果两个字符串的冒泡排序排成升序的次数奇偶性相同,那么可以转换成相同的字符串,反之不行。
  • 因为每次调换你可以强制相邻的两项,每次调换都会改变次数的奇偶性。
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 30;
int a[maxn], b[maxn];
int n; int calc(string s)
{
int cnt = 0;
for(int i = 0; i < n-1; i++)
for(int j = 0; j < n - i; j++)
if(s[j] > s[j+1])
{
cnt++;
swap(s[j], s[j+1]);
}
return cnt % 2;
} int main()
{
int T;
cin >> T;
while(T--)
{
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
string s, t;
cin >> n >> s >> t;
for(int i = 0; i < n; i++)
{
a[s[i]-'a']++;
b[t[i]-'a']++;
} bool flag = 1;
bool jud = 0;
for(int i = 0; i < 26; i++)
{
if(a[i] != b[i]) {
flag = 0;
break;
} if(a[i] > 1) jud = 1;
} if(!flag) {
puts("NO");
continue;
}
if(jud) {
puts("YES");
continue;
} if(calc(s) == calc(t)) puts("YES");
else puts("NO");
} return 0;
}

CF598: div3解题报告的更多相关文章

  1. 12&period;27 cf div3 解题报告

    12.27 cf div3 解题报告 wxy.wxy,带上分拉,全场做了个无脑小白 比赛场地 A: T1,跟着模拟就好了 B: sort一遍之后 去除的数一定是a[1]或者a[n] 比较去除谁小就输出 ...

  2. CH Round &num;56 - 国庆节欢乐赛解题报告

    最近CH上的比赛很多,在此会全部写出解题报告,与大家交流一下解题方法与技巧. T1 魔幻森林 描述 Cortana来到了一片魔幻森林,这片森林可以被视作一个N*M的矩阵,矩阵中的每个位置上都长着一棵树 ...

  3. 二模13day1解题报告

    二模13day1解题报告 T1.发射站(station) N个发射站,每个发射站有高度hi,发射信号强度vi,每个发射站的信号只会被左和右第一个比他高的收到.现在求收到信号最强的发射站. 我用了时间复 ...

  4. BZOJ 1051 最受欢迎的牛 解题报告

    题目直接摆在这里! 1051: [HAOI2006]受欢迎的牛 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 4438  Solved: 2353[S ...

  5. 习题:codevs 2822 爱在心中 解题报告

    这次的解题报告是有关tarjan算法的一道思维量比较大的题目(真的是原创文章,希望管理员不要再把文章移出首页). 这道题蒟蒻以前做过,但是今天由于要复习tarjan算法,于是就看到codevs分类强联 ...

  6. 习题:codevs 1035 火车停留解题报告

    本蒟蒻又来写解题报告了.这次的题目是codevs 1035 火车停留. 题目大意就是给m个火车的到达时间.停留时间和车载货物的价值,车站有n个车道,而火车停留一次车站就会从车载货物价值中获得1%的利润 ...

  7. 习题: codevs 2492 上帝造题的七分钟2 解题报告

    这道题是受到大犇MagHSK的启发我才得以想出来的,蒟蒻觉得自己的代码跟MagHSK大犇的代码完全比不上,所以这里蒟蒻就套用了MagHSK大犇的代码(大家可以关注下我的博客,友情链接就是大犇MagHS ...

  8. 习题:codevs 1519 过路费 解题报告

    今天拿了这道题目练练手,感觉自己代码能力又增强了不少: 我的思路跟别人可能不一样. 首先我们很容易就能看出,我们需要的边就是最小生成树算法kruskal算法求出来的边,其余的边都可以删掉,于是就有了这 ...

  9. NOIP2016提高组解题报告

    NOIP2016提高组解题报告 更正:NOIP day1 T2天天爱跑步 解题思路见代码. NOIP2016代码整合

随机推荐

  1. ajax将json写到table中去

    查询条件: <table style="width: 100%;border-collapse: collapse;" > <tr> <th styl ...

  2. Android的selector,背景选择器

    原文地址 http://android.blog.51cto.com/268543/564581 首先android的selector是在drawable/xxx.xml中配置的,相关图片放在同目录下 ...

  3. SQLite入门与分析&lpar;四&rpar;---Page Cache之事务处理&lpar;3&rpar;

    写在前面:由于内容较多,所以断续没有写完的内容. 11.删除日志文件(Deleting The Rollback Journal)一旦更改写入设备,日志文件将会被删除,这是事务真正提交的时刻.如果在这 ...

  4. &lbrack;Q&rsqb;关于无法进入主界面问题解答

    打图精灵适用于AutoCAD2007或更高版,低于2007版无法使用. 若在安装打图精灵前AutoCAD已经打开,则需要将AutoCAD重新打开,然后使用“QPlot”命令. 若重新打开仍然调不出界面 ...

  5. 负载均衡LVS&lpar;DR模式&rpar;安装实战

    1.编译安装ipvsadm 首先从LVS官网下载tarball,解压后make && make install即可. 要注意的是LVS的依赖有:popt-static.libnl.ke ...

  6. eclipse启动tomcat访问http&colon;&sol;&sol;localhost&colon;8080 报404错误

    eclipse正常启动tomcat,但是 访问http://localhost:8080 却报404错误 修改下配置 就好操作如下图 打开eclipse的server视图,双击配置好的那个tomcat ...

  7. centos7安装浏览器

    firefox(火狐) sudo yum install firefox chrome(谷歌) 添加源:sudo wget http://repo.fdzh.org/chrome/google-chr ...

  8. POJ 2752 Seek the Name&comma; Seek the Fame(KMP中next的理解)题解

    题意: 要求你给出每个前后缀相同的串的长度,比如: "alala"的前缀分别为{"a", "al", "ala", &q ...

  9. 架构-LAMP特级学习&lpar;网站大访问量解决方案&rpar;

    网站运营要面对的四个问题总结: 1.大访问量(主用负载均衡技术) 2.大存储量 3.访问速度 4.服务器监控 一.大访问量解决方案 超级计算机 = 负载均衡 + 集群 0.反向代理(Nginx等实现) ...

  10. CentOS 6&period;2修改主机名

    写在前面的话:因为服务器要统一主机名,但是在安装的时候忘记设置了,所以需要修改主机名   需要修改两处:一处是/etc/sysconfig/network,另一处是/etc/hosts,只修改任一处会 ...