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解题报告的更多相关文章
-
12.27 cf div3 解题报告
12.27 cf div3 解题报告 wxy.wxy,带上分拉,全场做了个无脑小白 比赛场地 A: T1,跟着模拟就好了 B: sort一遍之后 去除的数一定是a[1]或者a[n] 比较去除谁小就输出 ...
-
CH Round #56 - 国庆节欢乐赛解题报告
最近CH上的比赛很多,在此会全部写出解题报告,与大家交流一下解题方法与技巧. T1 魔幻森林 描述 Cortana来到了一片魔幻森林,这片森林可以被视作一个N*M的矩阵,矩阵中的每个位置上都长着一棵树 ...
-
二模13day1解题报告
二模13day1解题报告 T1.发射站(station) N个发射站,每个发射站有高度hi,发射信号强度vi,每个发射站的信号只会被左和右第一个比他高的收到.现在求收到信号最强的发射站. 我用了时间复 ...
-
BZOJ 1051 最受欢迎的牛 解题报告
题目直接摆在这里! 1051: [HAOI2006]受欢迎的牛 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 4438 Solved: 2353[S ...
-
习题:codevs 2822 爱在心中 解题报告
这次的解题报告是有关tarjan算法的一道思维量比较大的题目(真的是原创文章,希望管理员不要再把文章移出首页). 这道题蒟蒻以前做过,但是今天由于要复习tarjan算法,于是就看到codevs分类强联 ...
-
习题:codevs 1035 火车停留解题报告
本蒟蒻又来写解题报告了.这次的题目是codevs 1035 火车停留. 题目大意就是给m个火车的到达时间.停留时间和车载货物的价值,车站有n个车道,而火车停留一次车站就会从车载货物价值中获得1%的利润 ...
-
习题: codevs 2492 上帝造题的七分钟2 解题报告
这道题是受到大犇MagHSK的启发我才得以想出来的,蒟蒻觉得自己的代码跟MagHSK大犇的代码完全比不上,所以这里蒟蒻就套用了MagHSK大犇的代码(大家可以关注下我的博客,友情链接就是大犇MagHS ...
-
习题:codevs 1519 过路费 解题报告
今天拿了这道题目练练手,感觉自己代码能力又增强了不少: 我的思路跟别人可能不一样. 首先我们很容易就能看出,我们需要的边就是最小生成树算法kruskal算法求出来的边,其余的边都可以删掉,于是就有了这 ...
-
NOIP2016提高组解题报告
NOIP2016提高组解题报告 更正:NOIP day1 T2天天爱跑步 解题思路见代码. NOIP2016代码整合
随机推荐
-
ajax将json写到table中去
查询条件: <table style="width: 100%;border-collapse: collapse;" > <tr> <th styl ...
-
Android的selector,背景选择器
原文地址 http://android.blog.51cto.com/268543/564581 首先android的selector是在drawable/xxx.xml中配置的,相关图片放在同目录下 ...
-
SQLite入门与分析(四)---Page Cache之事务处理(3)
写在前面:由于内容较多,所以断续没有写完的内容. 11.删除日志文件(Deleting The Rollback Journal)一旦更改写入设备,日志文件将会被删除,这是事务真正提交的时刻.如果在这 ...
-
[Q]关于无法进入主界面问题解答
打图精灵适用于AutoCAD2007或更高版,低于2007版无法使用. 若在安装打图精灵前AutoCAD已经打开,则需要将AutoCAD重新打开,然后使用“QPlot”命令. 若重新打开仍然调不出界面 ...
-
负载均衡LVS(DR模式)安装实战
1.编译安装ipvsadm 首先从LVS官网下载tarball,解压后make && make install即可. 要注意的是LVS的依赖有:popt-static.libnl.ke ...
-
eclipse启动tomcat访问http://localhost:8080 报404错误
eclipse正常启动tomcat,但是 访问http://localhost:8080 却报404错误 修改下配置 就好操作如下图 打开eclipse的server视图,双击配置好的那个tomcat ...
-
centos7安装浏览器
firefox(火狐) sudo yum install firefox chrome(谷歌) 添加源:sudo wget http://repo.fdzh.org/chrome/google-chr ...
-
POJ 2752 Seek the Name, Seek the Fame(KMP中next的理解)题解
题意: 要求你给出每个前后缀相同的串的长度,比如: "alala"的前缀分别为{"a", "al", "ala", &q ...
-
架构-LAMP特级学习(网站大访问量解决方案)
网站运营要面对的四个问题总结: 1.大访问量(主用负载均衡技术) 2.大存储量 3.访问速度 4.服务器监控 一.大访问量解决方案 超级计算机 = 负载均衡 + 集群 0.反向代理(Nginx等实现) ...
-
CentOS 6.2修改主机名
写在前面的话:因为服务器要统一主机名,但是在安装的时候忘记设置了,所以需要修改主机名 需要修改两处:一处是/etc/sysconfig/network,另一处是/etc/hosts,只修改任一处会 ...