Codeforces Round #394 (Div. 2) 题解
题目连接：http://codeforces.com/contest/761
A. Dasha and Stairs
解题思路：
判断一下两者相减的绝度值是否为小于2。注意特判两个0的情况
时间复杂度：O(1)
空间复杂度：O(1)
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int n,m;
int main()
{
cin >> n>>m;
if(n==0&&m==0)
{
cout << "NO"<<endl;
return 0;
}
if(abs(n-m)<=1)
{
cout << "YES"<<endl;
}
else
{
cout << "NO"<<endl;
}
return 0;
} B - Dasha and friends
题目大意
给两个序列描述圆上的点，判断这两个圆是否可以视为同一个圆。
解题思路：
暴力搜索，两个序列元素分别一一对应，直到找到所有点距离都相同的情况。注意环形特征- ->取余
时间复杂度：O(n^2)
空间复杂度：O(n)
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
typedef vector<int> vi;
int judge(int x);
int n,l;
vi a,b;
int main()
{
int t;
cin >> n>>l;
rep(i,1,n)
{
cin >> t;
a.push_back(t);
}
rep(i,1,n)
{
cin >> t;
b.push_back(t);
}
for(int i=0;i<n;i++)
{
if(judge(i))
{
cout <<"YES"<<endl;
return 0;
}
}
cout <<"NO"<<endl;
return 0;
}
int judge(int x)
{
int xx ;
if(a[0]<b[(x)%n])
{
xx = a[0]+l-b[(x)%n];
}
else
{
xx = a[0]-b[(x)%n];
}
//cout <<xx<<endl;
for(int i=1;i<n;i++)
{
int yy ;
if(a[i]<b[(i+x)%n])
{
yy = a[i]+l-b[(i+x)%n];
}
else
{
yy =a[i]- b[(i+x)%n];
}
if(yy!=xx)
{
// cout << i<<" "<<x<<endl;
return 0;
}
}
return 1;
} C. Dasha and Password
题目大意
在多个字符串中组成一个符合条件的密码，问最小移动次数
解题思路：
对三种情况暴力搜索，分别找到最小，注意判断三者最小是否在一个字符串上。
时间复杂度：O(n^2)
空间复杂度：O(n)
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
typedef vector<int> vi;
int n,m;
vector<string> a;
int ffb=-1,ffc=-1,ffd=-1;
string s;
int b,c,d,b1,b2,c1,c2,d1,d2;
int main()
{
cin >>n>>m;
rep(i,1,n)
{
cin >> s;
if(s[0]=='#'||s[0]=='*'||s[0]=='&')
{
ffd = i-1;
d++;//计数
}
else if(s[0]>='0'&&s[0]<='9')
{
ffc =i-1;
c++;//计数
}
else
{
ffb = i-1;
b++;
}
a.push_back(s);
}
int ct =0;
//cout << b<<" "<<c<<" "<<d<<endl;
//如果只有一个字符串满足条件，，删去
if(b==1)
{
a.erase(a.begin()+ffb);
n--;
}
if(c==1)
{
a.erase(a.begin()+ffc);
n--;
}
if(d==1)
{
a.erase(a.begin()+ffd);
n--;
}
//遍历找最小移动次数，找到后删除，防止重复
if(b==0)
{
ct++;
int tt= inf_int;
for(int i=0;i<n;i++)
{
int t=0;
//s.clear();
s = a[i];
for(int j1=0,j2=0;j1!=j2||t==0;)
{
t++;
j1 = (j1-1+m)%m;
j2 = (j2+1)%m;
if(s[j1]>='a'&&s[j1]<='z'
||s[j2]>='a'&&s[j2]<='z')
{
if(tt>t)
{
b1 = i;
tt= t;
break;
}
}
}
// cout <<tt<<endl;
}
if(tt==inf_int)
tt=0;
b2 = tt;
if(b2!=0)
{
a.erase(a.begin()+b1);
n--;
}
}
if(c==0)
{
ct++;
int tt= inf_int;
for(int i=0;i<n;i++)
{
int t=0;
s = a[i];
for(int j1=0,j2=0;j1!=j2||t==0;)
{
t++;
j1 = (j1-1+m)%m;
j2 = (j2+1)%m;
if(s[j1]>='0'&&s[j1]<='9'
||s[j2]>='0'&&s[j2]<='9')
{
if(tt>t)
{
c1 = i;
tt= t;
break;
}
}
}
}
if(tt==inf_int)
tt=0;
c2=tt;
if(c2!=0)
{
a.erase(a.begin()+c1);
n--;
}
}
if(d==0)
{
ct++;
int tt= inf_int;
for(int i=0;i<n;i++)
{
int t=0;
s = a[i];
for(int j1=0,j2=0;j1!=j2||t==0;)
{
t++;
j1 = (j1-1+m)%m;
j2 = (j2+1)%m;
if(s[j1]=='#'||s[j1]=='*'||s[j1]=='&'
||s[j2]=='#'||s[j2]=='*'||s[j2]=='&')
{
if(tt>t)
{
d1 = i;
tt= t;
break;
}
}
}
}
if(tt==inf_int)
tt=0;
d2=tt;
if(d2!=0)
{
a.erase(a.begin()+d1);
n--;
}
}
if(ct==0)
{
cout <<0<<endl;
return 0;
}
else if(ct==1)
{
cout << b2+c2+d2<<endl;
return 0;
}
else
{
if(b)
{
cout << c2+d2<<endl;
return 0;
}
else if(c)
{
cout << b2+d2<<endl;
return 0;
}
else
{
cout << b2+c2<<endl;
return 0;
}
}
return 0;
}
D. Dasha and Very Difficult Problem
题目大意
p数组代表数组c的大小排列，而且c中元素互不相同，c[i] = b[i]-a[i],
a,b,元素大小限制为 l ≤ ai ，bi≤ r
给定数组a，求满足条件的数组b
解题思路：
贪心，首先找出c中最大的元素，然后给相应的b赋值为r，然后按照元素大小，按照每次c减小1的做法求出b，如果b大于r ，则取b为r，如果b小于l，则不符合条件，输出-1 。
时间复杂度：O(n*log(n))
空间复杂度：O(n)
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
typedef vector<int> vi;
const int N = 1e5+5;
typedef struct node{
int x;
int index;
}NODE;
bool cmp(NODE x,NODE y)
{
return x.x>y.x;
}
int n,l,r;
int a[N];
NODE p[N];
int b[N];
set<int> se;
int main()
{
cin >>n>>l>>r;
rep(i,1,n)
{
cin >> a[i];
}
rep(i,1,n)
{
cin >> p[i].x;
p[i].index = i;
}
sort(p+1,p+n+1,cmp);
b[p[1].index] = r;
rep(i,2,n)
{
int tt = a[p[i].index]+b[p[i-1].index]-a[p[i-1].index]-1;
if(tt>r)
{
b[p[i].index] = r;
}
else if(tt>=l)
{
b[p[i].index] = tt;
}
else
{
cout <<-1<<endl;
return 0;
}
}
rep(i,1,n)
{
cout << b[i]<<" ";
}
cout <<endl;
return 0;
} E. Dasha and Puzzle(构造题+DFS)
题目大意
给定一颗树，判断其在笛卡尔平面内，是否有边与坐标平行，且不相交的情况。
解题思路：
如果有一个顶点的出度超过4，则不满足题意。
否则根据长度构造树，使每层的长度有较大差距，就保证了其不相交。
利用DFS放点。我用的是对2的幂级来确定长度。
时间复杂度：O(n)
空间复杂度：O(n)
代码如下：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
typedef vector<int> vi;
int dir[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
const ll N = 1e18;
typedef struct node{
ll x;
ll y;
}NODE;
void dfs(int x,int chang,int dr);
int flag = 0;
int book1[40];
int n,u,v;
int in[40];
NODE pos[40];
int ct = 0;
vi mpp[40];
int main()
{
cin >>n;
rep(i,1,n-1)
{
cin >> u>> v;
in[v]++;
mpp[u].push_back(v);
mpp[v].push_back(u);
}
rep(i,1,n)
{
if(mpp[i].size()>4)
{
cout <<"NO"<<endl;
return 0;
}
}
rep(i,1,n)
{
if(in[i]==0)
{
pos[i].x = N/2;
pos[i].y = N/2;
book1[i]= 1;
dfs(i,40,-100);
break;
}
}
cout <<"YES"<<endl;
rep(i,1,n)
cout << pos[i].x<<" "<<pos[i].y <<endl;
return 0;
}
void dfs(int x,int chang,int dr)
{
ct =0;
for(int i=1;i<=n;i++)
{
ct += book1[i];
}
//cout <<ct<<endl;
if(flag) return ;
if(ct>=n)
{
flag = 1;
return ;
}
for(int i=0;i<4;i++)
{
if((dr+2)%4==i) continue;
for(int k=0;k<mpp[x].size();k++)
{
if(book1[mpp[x][k]]==1) continue;
ll xx = pos[x].x + dir[i][0]*(((ll)1<<chang)*100-3*mpp[x][k]);
ll yy = pos[x].y + dir[i][1]*(((ll)1<<chang)*100-3*mpp[x][k]);
book1[mpp[x][k]]=1;
// cout << mpp[x][k]<<endl;
pos[mpp[x][k]].x = xx;
pos[mpp[x][k]].y = yy;
dfs(mpp[x][k],chang-1,i);
break;
}
}
}