这场D题的思维又不会写 2333
A. Points in Segments
给出n个区间，求出1~m中有多少点没有没任意一个区间覆盖
数据范围小，数组标记即可
#include<bits/stdc++.h>
using namespace std;
int f[110];
int main(){
int n,m;
cin>>n>>m;
for(int i=1,l,r;i<=n;++i){
cin>>l>>r;
while(l<=r) {
f[l++]=1;
}
}
int cnt=0;
for(int i=1;i<=m;++i){
if(!f[i]) ++cnt;
}
cout<<cnt<<endl;
for(int i=1;i<=m;++i){
if(!f[i]) cout<<i<<" ";
}
return 0;
}
B. Obtaining the String
两个相邻的字母可以交换位置，求s变成t的任意操作方案
string暴力模拟
#include<bits/stdc++.h>
using namespace std;
string s,t;
vector<int> ans;
int main(){
int n;
cin>>n;
cin>>s>>t;
bool f=1;
for(int i=0,j=0;j<n;++j,++i){
if(s[i]!=t[j]){
int ff=0;
int k;
for(k=i;k<n;++k){
if(s[k]==t[j]){
s.erase(s.begin()+k);
s.insert(s.begin()+i,t[j]);
ff=1;
break;
}
}
if(ff==0){
f=0;
break;
}
for(int l=k-1;l>=i;--l){
ans.push_back(l);
}
}
}
if(!f) cout<<"-1";
else {
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();++i) cout<<ans[i]+1<<" ";
}
return 0;
}
D. Walking Between Houses
由1~n个房子排成一列，你需要从1号房子出发，走k次，每次可以走任意步数，但是只能一个方向，并且也不能走出1~n的范围，你需要走k次后恰好移动s步，输出是否可行以及可行的方案
首先确定NO的条件是：k*(n-1)<s或k>s。每次走s/k步，k次即走了[s/k]*k步，还剩下s%k步没走，再把这剩余的s%k步分到任意次里，即有s%k次走了s/k+1步，（s/k+1不会超出n-1，因为k>=s/(n-1)，当=时s%(n-1)=0，也就不需要多走那1步了
#include<iostream>
using namespace std;
int main(){
long long n,k,s;
cin>>n>>k>>s;
if (k*(n-1)<s||k>s){
cout<<"NO";
return 0;
}
cout<<"YES
";
long long t=1;
for (int i=1;i<=s%k;i++){
if (i&1)
t=s/k+2;
else
t=1;
cout<<t<<' ';
}
for(int i=s%k+1;i<=k;i++){
if (t<=(s/k))
t+=s/k;
else
t-=s/k;
cout<<t<<' ';
}
return 0;
}
E1. Stars Drawing (Easy Edition)
给一个n*m的矩阵，'.'表示空白,'*'表示某种物质，多个'*'组合成一个四条边长相等的十字形状的星星，求出所有星星的构造方案，使得每个'*'都至少被一个星星包含，星星的数量不能超过n*m ，(3<=n,m<=100)
由于星星的数量最大可以到n*m，所以贪心在每'*'构造一个星星，并且让这个星星的边长尽可能地最大以覆盖最多的物质
#include<bits/stdc++.h>
using namespace std;
string s,t;
vector<int> ans;
int main(){
int n;
cin>>n;
cin>>s>>t;
bool f=1;
for(int i=0,j=0;j<n;++j,++i){
if(s[i]!=t[j]){
int ff=0;
int k;
for(k=i;k<n;++k){
if(s[k]==t[j]){
s.erase(s.begin()+k);
s.insert(s.begin()+i,t[j]);
ff=1;
break;
}
}
if(ff==0){
f=0;
break;
}
for(int l=k-1;l>=i;--l){
ans.push_back(l);
}
}
}
if(!f) cout<<"-1";
else {
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();++i) cout<<ans[i]+1<<" ";
}
return 0;
}