第十七届中国计量大学程序设计竞赛（同步赛）-部分题解（B,C,F,H,I,K）
第十七届中国计量大学程序设计竞赛（同步赛）-部分题解（B,C,F,H,I,K）
B：Broken Pad
题意
多组输入，每次输入t组数据；每组数据给定两个字符串，分别为操作串和目标串。共有两种操作方法：
- 对于任意位置选择当前位置的纸牌进行翻转，由于按钮坏了，于是包括当前位置以及它后面的所有纸牌都会翻转。
- 可以选择空白区域（注意：题目有点难懂，并不是字符串中的0，而是理解为空白区域）进行操作，使得操作串所有的字符都变成0.
现需要求：最少操作次数，使得操作串等于目标串。
题意
分析两种操作，可以考虑两种情况：
- 直接不考虑将所有的字符都转成0，而是只进行操作一，计算出需要的操作次数，并将操作情况存到一动态数组中。
- 首先将操作串初始化为0（即：进行操作二），然后进行操作一，计算出需要的操作次数，并将操作情况存到另一个动态数组中。
从这两种情况取最优情况即可。
AC代码（cpp）
#include<cstdio>
#include<vector>
#include<map>
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#define lowbit x x&(-x)
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int maxn=1e5+5;
const ll mod=1e9+7;
char s1[maxn],s2[maxn];
vector<int>ve1,ve2;
int main() {
int t,len;
while(~scanf("%d",&t)) {
while(t--) {
ve1.clear();ve2.clear();
scanf("%s",s1+1);
scanf("%s",s2+1);
int len=strlen(s1+1);
int flag=0;
for(int i=1; i<=len; i++) {
if(s1[i]!=s2[i]&&!flag) {
flag=1;
ve1.push_back(i);
} else if(s1[i]==s2[i]&&flag) {
flag=0;
ve1.push_back(i);
}
}
for(int i=1;i<=len;i++) s1[i]='0';
flag=0;
for(int i=1; i<=len; i++) {
if(s1[i]!=s2[i]&&!flag) {
flag=1;
ve2.push_back(i);
} else if(s1[i]==s2[i]&&flag) {
flag=0;
ve2.push_back(i);
}
}
if(ve2.size()<ve1.size()) {
printf("0");
for(int i=0; i<ve2.size(); i++) {
printf(" %d",ve2[i]);
}
printf("\n");
}else{
for(int i=0;i<ve1.size();i++){
printf("%d%c",ve1[i],i==ve1.size()-1?'\n':' ');
}
}
}
}
return 0;
}
C：Cook Steak
题意
多组输入，每组输入数据给定一整数n，表示n个步骤。接着给定每个步骤需要的温度区间。求最少需要多少分钟使得牛排烤成功。
题解
有个坑点：步骤不能排序，而是按照它给定的顺序进行操作。
首先对于第一个操作，当然是将温度调到最小的温度为最优，记录当前温度
然后遍历第2~第n个操作，分别计算上一温度与当前操作最小温度以及最大温度的差值，从中选择差值小的，将温度调到对应差值小的温度，然后更新当前温度，方便下一操作判断。
具体见代码。
AC代码（cpp）
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
const int mod=1000000;
struct node {
ll x,y;
};
node a[maxn];
int t,n;
int main() {
while(~scanf("%d",&t)) {
while(t--) {
scanf("%d",&n);
memset(a,0,sizeof(a));
for(int i=1; i<=n; i++) scanf("%lld%lld",&a[i].x,&a[i].y);
ll ans=a[1].x+1;
ll num=a[1].x;
for(int i=2; i<=n; i++) {
if(num>=a[i].x&&num<=a[i].y){
ans++;continue;
}
if(abs(a[i].x-num)<=abs(a[i].y-num)) {
ans+=(abs(a[i].x-num)+1);
num=a[i].x;
} else {
ans+=(abs(a[i].y-num)+1);
num=a[i].y;
}
}
printf("%lld\n",ans);
}
}
return 0;
}
F：Flag Scramble Competition
题意
直接计算题目描述中出现最多的字母，输出相应字母（不区分大小写）
题解
签到题，最终计算是e，于是直接输出e即可。
#include<cstdio>
#include<vector>
#include<map>
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#define lowbit x x&(-x)
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int maxn=1e5+5;
const ll mod=1e9+7;
char s[maxn];
map<char,int>mp;
int main(){
printf("e\n");
return 0;
}
H：Happy Time is Always Short
题意
多组输入，每组输入数据给定n个人的value值，然后有m个操作，每次操作给定l,r表示区间[l,r]，即区间[l,r]的人将离开，然后计算剩余人中value值最大的，并输出最大value值。
题解
很明显一道数据结构题：区间修改&区间查询。
于是直接用线段树维护即可。
AC代码（cpp）
#include<cstdio>
#include<vector>
#include<map>
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#define lowbit x x&(-x)
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int maxn=1e5+5;
const ll mod=1e9+7;
const int maxnode = (1e5+5)*4;
int _max, op, qL, qR, v;
struct IntervalTree {
int maxv[maxnode], setv[maxnode];
// 维护信息
void maintain(int o, int L, int R) {
int lc = o*2, rc = o*2+1;
if(R > L) {
maxv[o] = max(maxv[lc], maxv[rc]);
}
if(setv[o] >= 0) {
maxv[o] = setv[o];
}
}
// 标记传递
void pushdown(int o) {
int lc = o*2, rc = o*2+1;
if(setv[o] >= 0) { //本结点有标记才传递。注意本题中set值非负，所以-1代表没有标记
setv[lc] = setv[rc] = setv[o];
setv[o] = -1; // 清除本结点标记
}
}
void update(int o, int L, int R) {
int lc = o*2, rc = o*2+1;
if(qL <= L && qR >= R) { // 标记修改
setv[o] = v;
} else {
pushdown(o);
int M = L + (R-L)/2;
if(qL <= M) update(lc, L, M);
else maintain(lc, L, M);
if(qR > M) update(rc, M+1, R);
else maintain(rc, M+1, R);
}
maintain(o, L, R);
}
void query(int o, int L, int R) {
if(setv[o] >= 0) { // 递归边界1：有set标记
_max = max(_max, setv[o]);
} else if(qL <= L && qR >= R) { // 递归边界2：边界区间
_max = max(_max, maxv[o]);
} else { // 递归统计
int M = L + (R-L)/2;
if(qL <= M) query(o*2, L, M);
if(qR > M) query(o*2+1, M+1, R);
}
}
};
IntervalTree tree;
int main() {
int n, m,t;
while(~scanf("%d",&t)) {
while(t--) {
scanf("%d%d",&n,&m);
memset(&tree, 0, sizeof(tree));
memset(tree.setv, -1, sizeof(tree.setv));
scanf("%d",&v);
tree.setv[1] = v;
for(int i=2;i<=n;i++){
scanf("%d",&v);
qL=i;qR=i;
tree.update(1,1,n);
}
while(m--) {
scanf("%d%d",&qL, &qR);
v=0;
tree.update(1,1,n);
_max = -inf;
int l=qL,r=qR;
qL=1;qR=l-1;
tree.query(1, 1, n);
qL=r+1;qR=n;
tree.query(1,1,n);
printf("%d\n",_max);
}
}
}
return 0;
}
I：Isolated Pointset
题意
n个点，判断是否存在任意两点的中垂线必过其他的的一点。
题解
其实这题是：祖冲之点集问题，但是稍微猜一下也是能过的。
具体怎么构造呢，可以考虑正三角形某一顶点在圆心，然后其他正三角形都有一顶点在圆心（即：共顶点三角形），见下图：
只要n>=3时，无论如何都能构造出符合条件的情况。
AC代码（cpp）
#include<cstdio>
#include<vector>
#include<map>
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#define lowbit x x&(-x)
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int maxn=1e5+5;
const ll mod=1e9+7;
int t,n;
int main() {
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
if(n>=3) printf("Yes\n");
else printf("No\n");
}
return 0;
}
K：Known-Well Palindrome Date-Easy Version
题意
多组数据，每组数据给定一字符串，求：字符串是否存在回文日期子串。
题解
- 首先考虑子串问题：直接可以用一滑动窗口维护即可
- 回文子串问题：直接遍历判断即可
- 回文日期子串：复杂点在此。
- 首先考虑日期在0001.01.01~9999.12.31之间；
- 然后考虑闰年情况，以及含31号和不含31号的月份情况
- 看似可以了，但是并没有考虑月份或日期为0的情况（这里我就wa了一发）
解决上述问题后，题目就简单了
AC代码（cpp）
#include<cstdio>
#include<vector>
#include<map>
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#define lowbit x x&(-x)
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int maxn=1e5+5;
const ll mod=1e9+7;
char s[maxn];
char window[maxn];
int checkRui(int year){
if(year%4==0||(year%400!=0&&year%100==0)) return 1;
return 0;
}
int checkday(int year,int month,int day){
if(day==0||year==0||month==0) return 0;
if(checkRui(year)&&month==2&&day>29) return 0;
if(!checkRui(year)&&month==2&&day>28) return 0;
if((month==1||month==3||month==5||month==7||month==8||month==10||month==12)&&day>31) return 0;
if((month==4||month==6||month==9||month==11)&&day>30) return 0;
return 1;
}
int check(int l,int r){
for(int i=l;i<=r;i++){
if(window[i]==' ') return 0;
}
for(int i=l;i<=l+3;i++){
if(window[i]==window[r-i+l]) continue;
else return 0;
}
int num=0;
for(int i=l;i<=r;i++){
num=num*10+(window[i]-'0');
}
if(!(num>=10101&&num<=99991231)) return 0;
int year=(window[l]-'0')*1000+(window[l+1]-'0')*100+(window[l+2]-'0')*10+(window[l+3]-'0');
int month=(window[l+4]-'0')*10+(window[l+5]-'0');
if(month>12) return 0;
int day=(window[l+6]-'0')*10+(window[l+7]-'0');
if(!checkday(year,month,day)) return 0;
return 1;
}
int main(){
while(gets(s+1)){
if(strcmp(s+1,"#")==0) break;
int len=strlen(s+1);
int ans=0;
for(int i=1;i<=8;i++) window[i]=s[i];
int l=1,r=8;
//for(int i=l;i<=r;i++) cout<<window[i];
//cout<<endl;
if(check(l,r)){
ans++;
}
for(int i=9;i<=len;i++){
l++;r++;
window[r]=s[i];
//for(int i=l;i<=r;i++) cout<<window[i];
//cout<<endl;
//if(strcmp(window+l,"20200202")==0) cout<<window+l<<endl;
//for(int i=l;i<=r;i++) cout<<window[i];
//cout<<endl;
if(check(l,r)) ans++;
}
printf("%d\n",ans);
}
return 0;
}
其他题没看...
