2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing)
E. Evil Coordinate
思路：因为如果给定了起点和初始走法，其实我们的终点是一定确定的。我们不妨让上下左右的连着一块走，那么对于\(RLUD\)一共有\(4!\)种走法(全排列)，我们暴力枚举然后\(check\)就可以了。
为什么这样是对的？为什么一条路走到底就可以把所以情况考虑完全了？
其实答案走法有很多种，但是我们可以把答案的走法拼接成连续的走法，这样就可以实现了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
#define int long long
int a[25][5];
int cnt[5];
int tmp[5];
bool vis[5];
int cn = 0;
void dfs(int step)
{
if(step>4)
{
cn++;
for(int i = 1;i<=4;i++)
a[cn][i] = tmp[i];
return;
}
for(int i = 1;i<=4;i++)
{
if(!vis[i])
{
vis[i] = true;
tmp[step] = i;
dfs(step+1);
tmp[step] = 0;
vis[i] = false;
}
}
}
void init()
{
dfs(1);
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
init();
while(t--)
{
int mx,my;
cin>>mx>>my;
string s;
cin>>s;
int sz = s.size();
s = "?"+s;
memset(cnt,0,sizeof(cnt));
for(int i = 1;i <= sz;i++)
{
if(s[i]=='R')cnt[1]++;
else if(s[i]=='L')cnt[2]++;
else if(s[i]=='U')cnt[3]++;
else if(s[i]=='D')cnt[4]++;
}
//R1,L2,U3,D4
bool flag = false;
for(int i = 1;i<=24;i++)
{
bool ok = true;
int lastx = 0,lasty = 0;
int x = 0,y = 0;
for(int j = 1;j<=4;j++)
{
//cout<<"i = "<<i<<"\n";
// cout<<"a[i][j] = "<<a[i][j]<<"\n";
if(a[i][j]==1&&cnt[1]){
x+=cnt[1];
// cout<<" x = "<<x<<" lastx = "<<lastx<<"\n";
if(y==my)
{
if((lastx<=mx&&mx<=x)||(x<=mx&&mx<=lastx)){
ok = false;
}else lastx = x;
}
else lastx = x;
}
else if(a[i][j]==2&&cnt[2]){
x-=cnt[2];
if(y==my)
{
if((lastx<=mx&&mx<=x)||(x<=mx&&mx<=lastx)){
ok = false;
}else lastx = x;
}
else lastx = x;
}
else if(a[i][j]==3&&cnt[3]){
y += cnt[3];
if(x==mx)
{
if((lasty<=my&&my<=y)||(y<=my&&my<=lasty)){
ok = false;
}
else lasty = y;
}else lasty = y;
}
else if(a[i][j]==4&&cnt[4]){
y -= cnt[4];
if(x==mx)
{
if((lasty<=my&&my<=y)||(y<=my&&my<=lasty)){
ok = false;
}
else lasty = y;
}else lasty = y;
}
}
if(ok)
{
for(int j = 1;j<=4;j++)
{
for(int k = 1;k<=cnt[a[i][j]];k++)
{
if(a[i][j]==1)
cout<<"R";
else if(a[i][j]==2)
cout<<"L";
else if(a[i][j]==3)
cout<<"U";
else cout<<"D";
}
}
cout<<"\n";
flag = true;
break;
}
}
if(!flag)
cout<<"Impossible\n";
}
return 0;
}
F.Fireworks
思路：一开始我们想成了求平均期望，思路上有问题的，因为题目求的是最优的。是求最小期望花费。
我们要做\(x\)次点亮一次，那么这\(x\)次中至少有一个是完美的概率就是\((1-全部都不完美的概率)\)，那全部都不完美的概率就是\(q^x\)次方，即至少有一个是完美的概率是\(1-q^k\)。
期望制作轮数\(E(x)=\dfrac{1}{1-q^k}\)，期望时间：\(f(k) = (n\times k+m)\times E(x)\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const double eps = 1e-6;
double n,m,p,q;
double f(double x)
{
return (x*n+m)/(1.0-pow(q,x));
}
/*
3
1 1 5000
1 1 1
1 2 10000
*/
int main()
{
// ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
cin>>n>>m>>p;
p = 1.0*p/10000.0;
q = 1.0-p;
//cout<<"p = "<<p<<" q = "<<q<<endl;
ll l = 1,r = 1e9;
while(r-l>2)
{
int mid1 = l+(r-l)/3;
int mid2 = r-(r-l)/3;
if(f(mid1)<=f(mid2))r = mid2;
else l = mid1;
}
double ans = 1e18;
for(int i = l;i <= r;i++)
ans = min(ans,f(i));
printf("%.10lf\n",ans);
}
return 0;
}
K. K Co-prime Permutation
思路：因为每一个数一定和下一个数互质，注意\(1\)和所有数都互质。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,k;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>k;
if(k==0)cout<<-1<<"\n";
else{
for(int i = 1;i<=k-1;i++)
cout<<i+1<<" ";
cout<<1<<" ";
for(int i = k+1;i<=n;i++)
cout<<i<<" ";
}
return 0;
}
L. Let's Play Curling
思路：求连续的红色的最大数量。注意可能有重叠。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
set<int>a,b;
map<int,int>cnt;
int n,m;
cin>>n>>m;
for(int i = 1;i <= n; i++){
int x;
cin>>x;
a.insert(x);
cnt[x]++;
}
for(int i = 1;i <= m; i++){
int x;
cin>>x;
b.insert(x);
}
vector<int> v;
for(auto x:a)
v.push_back(x);
for(auto x:b)
v.push_back(x);
sort(v.begin(), v.end());
int tmp = 0,ans = 0;
int k = v.size();
for(int i = 0;i<k;i++)
{
if(a.find(v[i])!=a.end()&&b.find(v[i])==b.end())
tmp += cnt[v[i]];
else ans = max(ans,tmp),tmp = 0;
}
ans = max(ans,tmp);
if(ans==0)cout<<"Impossible\n";
else
cout<<ans<<"\n";
}
return 0;
}