感觉自己有点强迫症 不都写出来就找理由不写题解
http://codeforces.com/contest/1015 题目链接
A. Points in Segments
题目意思 n个线段 去覆盖1-m 中的点 问你没有覆盖的点的个数和位置
这个数据很小，可以直接暴力查找
思考：如果n<1e6, m<=1e8 呢？
#include<bits/stdc++.h>
#define int long long
#define MAX(a,b,c) max(a,max(b,c))
#define MIN(a,b,c) min(a,min(b,c))
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned long long uLL;
using namespace std;
const int maxn=1e5+;
const int INF=0x3f3f3f3f;
map<int,int> mp;
int32_t main()
{
int n,m;
cin>>n>>m;
for(int i=;i<=n;i++)
{
int a,b; cin>>a>>b;
for(int j=a;j<=b;j++)
mp[j]=;
}
int t=;
for(int i=;i<=m;i++)
{
if(mp[i]==)
{
t++;
}
}cout<<t<<endl;
for(int i=;i<=m;i++)
{
if(mp[i]==)
{
cout<<i<<" ";
}
}
}
A.cpp
如果 m<=1e8的 话，可以标记 线段的起点 重点后一位 左右搜一遍
如1-5 a[1]=1; a[6]=-1;
B. Obtaining the String
一个n,两个字符串(ss,tt)，左右移动前一个字符串 使两个字符串相等 求最小移动次数；
对比 ss ,tt 当ss[i] !=tt[i]; 在ss[i]后面找和tt[i]一样的， 移动到ss[i]；没有就输出-1；
#include<bits/stdc++.h>
#define int long long
#define MAX(a,b,c) max(a,max(b,c))
#define MIN(a,b,c) min(a,min(b,c))
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned long long uLL;
using namespace std;
const int maxn=1e5+;
const int INF=0x3f3f3f3f;
map<int,int> mp;
vector<int> pp;
int32_t main()
{
int n; cin>>n;
string ss,tt; cin>>ss; cin>>tt;
//if(ss==tt) { cout<<-1<<endl; return 0;}
int j=;
for(int i=;i<n;i++)
{
if(ss[j]==tt[i])
{
j++; continue;
}
int t=;
for(int k=j+;k<n;k++)
{ if(ss[k]==tt[i])
{
for(int x=k-;x>=j;x--)
{
swap(ss[x],ss[x+]);
t=;
pp.push_back(x+);
}
if(t==) { j++;break;}
}
}
if(t==) { cout<<-<<endl; return ;}
}
cout<<pp.size()<<endl;
for(int i=;i<pp.size();i++)
{
cout<<pp[i]<<" ";
}
}
B.cpp
C. Songs Compression
n 组数据 一开始的歌曲数据大小 压缩后的数据大小， 要是数据小于等于m;
直接计算一开始的大小，每次减去 差值最大的；看多少次后数据小于等于m; 压缩不到m就输出-1；
#include<bits/stdc++.h>
#define int long long
#define MAX(a,b,c) max(a,max(b,c))
#define MIN(a,b,c) min(a,min(b,c))
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned long long uLL;
using namespace std;
const int maxn=1e5+;
const int INF=0x3f3f3f3f;
int a[maxn];
int b[maxn];
int d[maxn];
int32_t main()
{
int n,m; cin>>n>>m; int ans1=; int ans2=;
for(int i=;i<=n;i++)
{
cin>>a[i]>>b[i];
d[i]=a[i]-b[i];
ans1+=a[i];
ans2+=b[i];
}
if(ans2>m) { cout<<-<<endl;return ;}
//if(ans1<=m) { cout<<0<<endl;return 0;}
sort(d+,d++n); int t=;
for(int i=n;i>=;i--)
{
if(ans1<=m) break;
ans1=ans1-d[i];
t++;
}
cout<<t<<endl;
}
C.cpp
D. Walking Between Houses
在1-n 中走 k次（随你走到哪，不能不走） 使走的路程为 s;
在保证每次都至少走一步的情况下 先走最大的 1 – n- 1 – n -1 -n….；
最后再每次走一步；
10 9 45 来说 每次走的距离为 9 9 9 9 5 1 1 1 1；
#include<bits/stdc++.h>
#define int long long
#define MAX(a,b,c) max(a,max(b,c))
#define MIN(a,b,c) min(a,min(b,c))
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned long long uLL;
using namespace std;
const int maxn=1e5+;
const int INF=0x3f3f3f3f;
int32_t main()
{
int n,k,s; cin>>n>>k>>s;
if(s>(n-)*k||s<k) { cout<<"NO"<<endl; return ;}
cout<<"YES"<<endl;
int t=;
while(s)
{
if(s-n+>=k-)
{
if(t%==) cout<<n<<" ";
else cout<<<<" ";
t++;
k--;
s=s-(n-); //cout<<s<<endl;
}
else
{
int d=s-(k-);// cout<<d<<endl;
int pos=;
if(t%==) { cout<<+d<<" "; pos=+d; }
else { cout<<n-d<<" "; pos=n-d;}
t++;
k--;
int x=;
while(k)
{
if(x%==)
{
if(pos->=) cout<<pos-<<" ";
else cout<<pos+<<" ";
}
else cout<<pos<<" ";
k--;
x++;
}
break;
}
}
}
D.cpp
E1. Stars Drawing (Easy Edition)
可以直接暴力搜 找到一个点 直接往上下左右搜 看照射的距离 大于1就全部标记
#include<bits/stdc++.h>
#define int long long
#define MAX(a,b,c) max(a,max(b,c))
#define MIN(a,b,c) min(a,min(b,c))
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned long long uLL;
using namespace std;
pair<int,int> pos[]={ {,},{,-},{,},{-,} };
bool tf[][];
char a[][];
int x2[];
int x1[];
int x3[];
int32_t main()
{
int n,m; cin>>n>>m; getchar();
for(int i=;i<n;i++)
gets(a[i]);
int t=;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(a[i][j]=='*')
{
//cout<<i<<" "<<j<<endl;
int z=;
while()
{
int x=;
for(int k=;k<;k++)
{
int x1=i+z*pos[k].first;
int y1=j+z*pos[k].second;
if(x1<||x1>=n||y1<||y1>=m)
{
continue;
}
if(a[x1][y1]=='*')
{
x++;
} }
//cout<<x<<endl;
if(x==)
{
tf[i][j]=;
for(int k=;k<;k++)
{
int x1=i+z*pos[k].first;
int y1=j+z*pos[k].second;
if(x1<||x1>=n||y1<||y1>=m)
{
continue;
}
if(a[x1][y1]=='*')
{
tf[x1][y1]=;
} }
}
else break;
z++;
}
if(z==) continue;
else
{
x1[t]=i;
x2[t]=j;
x3[t]=z-; t++;
}
}
}
} // cout<<t<<endl;
int k1=;
int k2=;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(a[i][j]=='*') k1++;
if(tf[i][j]==) k2++;
}
}
if(k1!=k2) cout<<-<<endl;
else
{
cout<<t<<endl;
for(int i=;i<t;i++)
{
cout<<x1[i]+<<" "<<x2[i]+<<" "<<x3[i]<<endl;
}
} //cout<<k1<<" "<<k2<<endl;
}
E1.cpp
E2. Stars Drawing (Hard Edition)
先预处理 每个点 上下左右 可以照射的距离 再标记
预处理有些技巧 ，不能暴力搜 要找相邻两个点的关系
由于预处理 和 标记 分开 不会超时;
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+;
int l[maxn][maxn];
int r[maxn][maxn];
int u[maxn][maxn];
int d[maxn][maxn];
int ans1[maxn*maxn];
int ans2[maxn*maxn];
int ans3[maxn*maxn];
char a[maxn][maxn];
bool f[maxn][maxn];
int main()
{
int n,m;
cin >> n >> m;
int i,j,s,y;
for (i = ; i <= n; i++)
for (j = ; j <= m; j++) cin >> a[i][j];
for (i = ; i <= n; i++) for (j = ; j <= m; j++)
if (a[i][j] == '*') l[i][j] = l[i][j-] + ; else l[i][j] = ; for (i = ; i <= n; i++) for (j = m; j >= ; j--)
if (a[i][j] == '*') r[i][j] = r[i][j+] + ; else r[i][j] = ; for (j = ; j <= m; j++) for (i = ; i <= n; i++)
if (a[i][j] == '*') u[i][j] = u[i-][j] + ; else u[i][j] = ; for (j = m; j >= ; j--) for (i = n; i >= ; i--)
if (a[i][j] == '*') d[i][j] = d[i+][j] + ; else d[i][j] = ; int t=;
for (i = ; i <= n; i++)
for (j = ; j <= m; j++) if (a[i][j] == '*') {
s = min(min(r[i][j+],l[i][j-]),min(u[i-][j],d[i+][j]));
if (s > ) {
ans1[t]=i; ans2[t]=j; ans3[t]=s; t++; for (y = j-s; y <= j+s; y++) f[i][y] = ;
for (y = i-s; y <= i+s; y++) f[y][j] = ;
}
}
for (i = ; i <= n; i++) for (j = ; j <= m; j++)
if (a[i][j] == '*' && f[i][j] == ) {
cout << - << endl;
return ;
}
cout<<t-<<endl;
for(int i=;i<=t-;i++)
cout<<ans1[i]<<" "<<ans2[i]<<" "<<ans3[i]<<endl;
}
E2.cpp
