做了几场CF的Div2级别的比赛，终于从这一场知道怎么上分了（因为自己很菜，还是1500+，所以上分很简单。。。）
先说说做题的心态：
A题B题，看完样例，看完特判，直接求手速，一般不会卡太多太难的数据
只需要保证：如果题目中有Hint好好看看，题目中有无法达成目标，然后需要输出-1或者无解信息的需要认真去想边界情况
然后CDEF的策略：
如果C和D题同分，那么先花上10分钟左右选题，把题目和样例读懂（这种比赛一般会是2个半小时6题甚至7题，我们的目标是保证3题，冲刺4题）
如果只有一个题有思路，那么没得挑
如果两个题在大概思路上都是会写的，而且觉得思路比较靠谱：那么我推荐：先做数据结构维护比较简单和熟悉的
（比如说这场的C和D）
C是一个看上去比较简单的构造题，然而需要先判断能否构造，再输出方案，还需要考虑到中间过程中节点位置和数目的变化，短时间不容易想清楚，比赛的时候先做的C题，幸好PP了（虽然最终挂了，但是给了我时间去写D）
D是一个我看错了题目的题：如果不看错题目，是个很简单的排序题
如果C和D不同分，那么我推荐硬着头皮做C题（因为只有2个小时，同时开2个题对我来说比较吃力，可能费力不讨好，一个都过不了）
如果还有能力和时间：
E题：如果觉得20分钟之内，能把代码写出来，而且比赛时间剩40分钟以上，那么我觉得去写是有意义的
有留给自己出样例，调试程序的时间
因为如果出不来这个题，不如把时间花在Lock了ABCD，然后去Hack别人的环节
当然，如果励志AK各种比赛的dalao
我这种弱菜就只能好好打自己的DIV2了，默默的不说话
如果愿意去Hack的：
我是建议先把C题和D题读完再去Hack：因为Hack其实是有风险的
在我认为我实力不够的情况下，把自己的A题和B题Lock了，而且Hack不到别人，自己的程序反而被别人Hack了不能再提交
那么这场就不用想着上分了
下面来认真说说这套题的ABCD四个题：
总体难度：A和B暴力模拟靠手速，C题有难度需要数学想法，D题看暴力思路
题目链接：codeforces733
这个题没有太多可说的，比赛的时候出现了一个很搞笑的事：没有判断Y字母的可以PP
维护当前元音字母，找下一个元音字母就可以
#include<bits/stdc++.h>
using namespace std;
bool ok(char x){
if (x=='A'||x=='E'||x=='I'||x=='O'||x=='U'||x=='Y') return true;
return false;
}
char s[500];
int main(){
int ans,n;
while(scanf("%s",s+1)!=EOF){
n=strlen(s+1);
ans=0;
int last=0;
for(int i=1;i<=n;i++)
if (ok(s[i])){
ans=max(ans,i-last);
//printf("%d\n",i-last);
last=i;
}
//printf("%d\n",n+1-last);
ans=max(ans,n+1-last);
printf("%d\n",ans);
}
return 0;
}
这个题也是个暴力题
求个和就好，然后再次扫一遍，每次求值去比较就好
细节点是要注意答案的初始化设为0是比较好的，因为最后如果有问题的话，也是要输出0的
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+500;
int n;
int l[maxn],r[maxn];
int suml,sumr;
int tmpl,tmpr;
int pos,ans;
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
suml=sumr=0;
for(int i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);
suml+=l[i];
sumr+=r[i];
}
pos=0;ans=abs(suml-sumr);
for(int i=1;i<=n;i++){
tmpl=suml-l[i]+r[i];
tmpr=sumr-r[i]+l[i];
if (abs(tmpl-tmpr)>ans){
pos=i;
ans=abs(tmpl-tmpr);
}
}
printf("%d\n",pos);
}
return 0;
}
这个题是自己比较自信的一个题：然后各种没有做好细节，带崩了
说下题意：
题目中会给n个数，这些数有其大小。大数可以把相邻的小数合并（大小是相对的）如果可以合并就可以一直合并
然后需要判断这n个数是不是有某个合并方案让其变成之后给的k个数
解释下样例：
6
1 2 2 2 1 2
2
5 5看到5和5，说明（1 2 2）是一组，（2 1 2）是另外一组
（1 2 2）合并成5是有方案的，虽然（2 2）不能合并，但是先合并成（3 2）就是可以变成5的啦
5
1 1 1 3 3
3
2 1 6再看这个，仍然是分组
（1 1）合并成2，无解
（1）就是对应1
（3 3）对应成6，无解
所以输出NO
所以，整体思路如下：
首先，将这n个数分成k组，这k组的和要与其输入的k个值一一对应
然后，如果每个组的数不是都相等（意味着有某个数可以不断的进行合并然后变成给定的值），那么输出YES，否则输出NO
这样是我的第一次想法，有HACK点：
A：没有判断n个数的和是不是等于k个数的和
B：每个组的数是不是都相等代码上怎么实现：如果某个组里只有一个元素，这个时候是可以构造的
C：最大值是怎么找到的，周围是不是都是最大值
结合上所有点HACK点，加上各种特判，说说自己怎么构造的：
在每个组里，找到可以去贪心的最大值：
可以的概念是：左边或者右边有值，而且这个值比我要小
贪心的概念是：如果找到的是左边：那么先把左边的数全部合并完毕；否则亦然
然后就是最麻烦的合并节点了：其实很好想清楚
当前已经处理好了m-1个组，现在在处理第m组，那么第m组的第一个数原来标号是什么？现在标号是什么？
因为前m-1个组已经合并好了，那么现在只占m-1个位置
原来有多少个位置，就看每个组里有多少个元素，加起来求个和就好了
那么标号的变化呢？
往左边吃，坐标吃完是要减1的。比如（1 2），吃完之后变成了（3），坐标有变化
往右边吃，坐标吃完是不变的。比如（2 1），吃完之后变成了（3），坐标没有变化
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int maxn=550;
int n,k;
int sum[maxn];
int sumpoint[maxn];
int a[maxn];
struct node{
int l,r;
int sum;
}b[maxn];
bool check(){
for(int i=1;i<=k;i++){
int len=b[i].r-b[i].l+1,tmp=0;
if (len==1) continue;
for(int j=b[i].l;j<=b[i].r;j++)
if (a[j]==a[b[i].l]) tmp++;
if (tmp==len) return false;
}
return true;
}
void print(int pos){
int i,maxnum=0,maxnumpos,len=b[pos].r-b[pos].l;
for(i=b[pos].l;i<=b[pos].r;i++)
if (a[i]>maxnum) maxnum=a[i];
for(i=b[pos].l;i<=b[pos].r;i++)
if (a[i]==maxnum){
if (i==b[pos].l){
if (a[i+1]<maxnum){
maxnumpos=i;
break;
}
}
else if (i==b[pos].r){
if (a[i-1]<maxnum){
maxnumpos=i;
break;
}
}
else{
if (a[i-1]<maxnum||a[i+1]<maxnum){
maxnumpos=i;
break;
}
}
}
i=maxnumpos;
if (i==b[i].r||(a[i]>a[i-1]&&i!=b[i].l)){
while(i!=b[pos].l){
printf("%d L\n",i-sumpoint[pos-1]);
i--;len--;
}
while(len){
printf("%d R\n",i-sumpoint[pos-1]);
len--;
}
}
else{
while(i!=b[pos].r){
printf("%d R\n",i-sumpoint[pos-1]);
len--;b[pos].r--;
}
while(i!=b[pos].l){
printf("%d L\n",i-sumpoint[pos-1]);
i--;len--;
}
}
}
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
int sumk=0;
sum[0]=0;sumpoint[0]=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=a[i]+sum[i-1];
}
scanf("%d",&k);
for(int i=1;i<=k;i++){
scanf("%d",&b[i].sum);
sumk+=b[i].sum;
}
if (sumk!=sum[n]){
puts("NO");
continue;
}
int s,i=1,j=1;
for(s=1;s<=n;s++)
if (sum[s]-sum[j-1]==b[i].sum){
b[i].l=j;
b[i].r=s;
sumpoint[i]=b[i].r-b[i].l+sumpoint[i-1];
j=s+1;
i++;
}
if (i!=k+1){
puts("NO");
continue;
}
/*
else{
for(i=1;i<=k;i++)
printf("%d %d %d\n",b[i].l,b[i].r,b[i].sum);
}
*/
if (check()){
puts("YES");
for(int i=1;i<=k;i++)
print(i);
}
else puts("NO");
}
return 0;
}
题目有句话特别重要：（自己***了没看到，写了三个排序，乱搞了好久，然后WA7了，又重写，至少浪费了500分）
In such gluing it is allowed to rotate and flip the stones in any way.
每个长方体是可以翻转的！
那么，我们可以按照x>=y>=z的方式来排序，如果（x，y）相同的，我们就合并z
因为要是球体，所以维护一个最大值就好，每次与min（x，y，z）比较取较大值
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+500;
int ans1,ans2,maxnum;
struct node{
int x,y,z,id;
}a[maxn];
int cmp(node aa,node bb){
if (aa.x==bb.x&&aa.y==bb.y) return aa.z<bb.z;
if (aa.x==bb.x) return aa.y<bb.y;
return aa.x<bb.x;
}
int Max,Min,n;
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
maxnum=0;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
a[i].id=i;
Max=max(a[i].x,max(a[i].y,a[i].z));
Min=min(a[i].x,min(a[i].y,a[i].z));
if (Min>maxnum){
maxnum=Min;
ans1=ans2=i;
}
a[i].y=a[i].x+a[i].y+a[i].z-Max-Min;
a[i].x=Max;
a[i].z=Min;
}
sort(a+1,a+n+1,cmp);
//for(int i=1;i<=n;i++)
// printf("%d %d %d\n",a[i].x,a[i].y,a[i].z);
for(int i=2;i<=n;i++)
if (a[i].x==a[i-1].x&&a[i].y==a[i-1].y){
Min=min(a[i].x,min(a[i].y,a[i].z+a[i-1].z));
if (Min>maxnum){
maxnum=Min;
ans1=a[i].id;
ans2=a[i-1].id;
}
}
if (ans1==ans2)
printf("1\n%d\n",ans1);
else
printf("2\n%d %d\n",ans1,ans2);
}
return 0;
}
京公网安备 11010502036488号