这是本人上大学后第二次参加算法类的比赛，可能也是准备不足的原因吧，导致我这次的发挥也依旧有些不尽人意，简单复盘了一下发现并没有那么难。我才大一，未来机会还很多，很可惜同队的学长是要退役毕业工作去了，对他我心里多少也有些愧对吧，祝他工作顺利吧，队里缺人有想来组队的吗。
E.Evil Coordinate
这道题类似于模拟，但我当时想的太复杂了，越写越乱，最后没时间了害，这道题其实就是让机器人去走直线去避开爆炸区，我考虑了好多好多种情况去一一的进行考虑，后来发现想多了。。。其实可以四个方向全排列挨个去试。。。还没从OI中脱离出来，思维还是原来的，硬伤啊，贴一下我那个很长很长的代码吧，我是智障
#include <bits/stdc++.h>
using namespace std;
char s[1000005];
void solve(){
int sx,sy,mx,my,l=0,r=0,d=0,u=0;
scanf("%d%d",&mx,&my);
scanf("%s",s+1);
int len=strlen(s+1);
for(int i=1;i<=len;i++){
if(s[i]=='U') u++;
if(s[i]=='D') d++;
if(s[i]=='R') r++;
if(s[i]=='L') l++;
}
sx=r-l,sy=u-d;
if(mx==0&&my==0){
printf("Impossible\n");
return;
}
if(sx==mx&&sy==my){
printf("Impossible\n");
return;
}
if(mx!=0&&my!=0){
if(mx==sx){
for(int i=1;i<=u;i++)
printf("U");
for(int i=1;i<=d;i++)
printf("D");
for(int i=1;i<=l;i++)
printf("L");
for(int i=1;i<=r;i++)
printf("R");
printf("\n");
return;
}
else{
for(int i=1;i<=l;i++)
printf("L");
for(int i=1;i<=r;i++)
printf("R");
for(int i=1;i<=u;i++)
printf("U");
for(int i=1;i<=d;i++)
printf("D");
printf("\n");
return;
}
}
if(mx==0){
if(sx==0){
if(!l&&!r&&((sy>0&&my>0&&sy>my)||(sy<0&&my<0&&sy<my))){
printf("Impossible\n");
return;
}
if(l) for(int i=1;i<=l;i++) printf("L");
else for(int i=1;i<=r;i++) printf("R");
if(my<0){
for(int i=1;i<=u;i++)
printf("U");
for(int i=1;i<=d;i++)
printf("D");
}
else{
for(int i=1;i<=d;i++)
printf("D");
for(int i=1;i<=u;i++)
printf("U");
}
if(l) for(int i=1;i<=r;i++) printf("R");
else for(int i=1;i<=l;i++) printf("L");
}
else{
for(int i=1;i<=l;i++)
printf("L");
for(int i=1;i<=r;i++)
printf("R");
for(int i=1;i<=u;i++)
printf("U");
for(int i=1;i<=d;i++)
printf("D");
}
}
if(my==0){
if(sy==0){
if(!u&&!d&&((sx>0&&mx>0&&sx>mx)||(sx<0&&mx<0&&sx<mx))){
printf("Impossible\n");
return;
}
if(u) for(int i=1;i<=u;i++) printf("U");
else for(int i=1;i<=d;i++) printf("D");
if(mx>0){
for(int i=1;i<=l;i++)
printf("L");
for(int i=1;i<=r;i++)
printf("R");
}
else{
for(int i=1;i<=r;i++)
printf("R");
for(int i=1;i<=l;i++)
printf("L");
}
if(u) for(int i=1;i<=d;i++) printf("D");
else for(int i=1;i<=u;i++) printf("U");
}
else{
for(int i=1;i<=u;i++)
printf("U");
for(int i=1;i<=d;i++)
printf("D");
for(int i=1;i<=l;i++)
printf("L");
for(int i=1;i<=r;i++)
printf("R");
}
}
printf("\n");
}
int main(){
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}
F. Fireworks
由于没学过概率论，只用高中那点知识来写期望表达式，结果就错了呜呜呜呜~~~期望计算方法为(n*x+m)/(1-(1-p,x)) (x为点燃烟花个数)，但为什么表达式是这样的和我高中所学的概率期望有所不同，等到时候我去学学概率论吧。这样一个表达式可以通过求二阶导来证明出这是个单谷函数，我们选择三分其谷值
#include <bits/stdc++.h>
using namespace std;
int T,n,m;
double p;
double cal(double x){
return (n*x+m)/(1.0-pow(1-p,x));
}
void solve(){
scanf("%d%d%lf",&n,&m,&p);
p*=1e-4;
double l=0,r=1e9;
while(r-l>1e-9){
double ll=l+(r-l)/3,rr=r-(r-l)/3;
if(cal(ll)<cal(rr)) r=rr;
else l=ll;
}
int ans=l;
printf("%.10f\n",min(cal(ans),cal(ans+1)));
}
int main(){
scanf("%d",&T);
while(T--)
solve();
return 0;
}
K. K Co-prime Permutation
相邻必互质！！！！
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[1000006],k;
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
a[i]=i;
if((k==0)||(k>n)){
printf("-1");
return 0;
}
for(int i=2;i<=k;i++)
printf("%d ",i);
printf("1");
for(int i=k+1;i<=n;i++)
printf(" %d",i);
return 0;
}
L. Let's Play Curling
这道题有点像一个脑筋急转弯，其实就是统计两个蓝队球之间有几个红队球，贴一份学长写的代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
int val;
int pos;
bool operator < (const node &n1){
if(pos == n1.pos){
return val > n1.val;
}
return pos < n1.pos;
}
};
int main(int argc, char const *argv[])
{
/* code */
int t, a, b;
cin >> t;
while(t--){
vector<node> vec;
cin >> a >> b;
while(a--){
node tmp;
tmp.val = 1;
cin >> tmp.pos;
vec.push_back(tmp);
}
while(b--){
node tmp;
tmp.val = 0;
cin >> tmp.pos;
vec.push_back(tmp);
}
sort(vec.begin(), vec.end());
int ans = 0;
int total = 0;
int len = vec.size();
for(int i=0;i<len;i++){
if(vec[i].val == 1){
total++;
}
if(vec[i].val == 0){
int tmp = i-1;
while(tmp>=0 && vec[tmp].pos == vec[i].pos){
tmp--;
total--;
}
ans = max(total, ans);
total = 0;
}
}
int lst = 0;
for(int i=len-1;i>=0;i--){
if(vec[i].val == 0){
lst = i;
break;
}
}
ans = max(ans, len-1-lst);
if(ans == 0){
cout << "Impossible" <<endl;
}else{
cout << ans << endl;
}
}
return 0;
}
M.Monster Hunter
一个树形dp问题，用dp[i][j][0/1]，第一维代表的是节点i，第二维代表的是节点i极其子节点有j个点被魔法杀掉了，第三维是代表i点有没有被魔法杀掉
#include <bits/stdc++.h>
#define inf 100000000000000
#define ll long long
using namespace std;
ll hp[5000],dp[4000][4000][2],siz[4000],g[4000][2];
vector<int>G[5000];
void dfs(int now,int fa){
siz[now]=1;
dp[now][0][0]=hp[now];
for(auto v:G[now]){
if(v==fa) continue;
dfs(v,now);
for(int i=0;i<=siz[now]+siz[v];i++) g[i][0]=g[i][1]=inf;
for(int i=0;i<=siz[now];i++){
for(int j=0;j<=siz[v];j++){
if(i+j<siz[now]+siz[v]){
g[i+j][0]=min(g[i+j][0],dp[now][i][0]+dp[v][j][0]+hp[v]);
if(j>0) g[i+j][0]=min(g[i+j][0],dp[now][i][0]+dp[v][j][1]);
}
if(i>0){
g[i+j][1]=min(g[i+j][1],dp[now][i][1]+dp[v][j][0]);
if(j>0) g[i+j][1]=min(g[i+j][1],dp[now][i][1]+dp[v][j][1]);
}
}
}
siz[now]+=siz[v];
for(int i=0;i<=siz[now];i++) dp[now][i][0]=g[i][0],dp[now][i][1]=g[i][1];
}
//for(int i=0;i<=siz[now];i++) dp[now][i][0]+=hp[now];
}
void solve(){
int n;
cin>>n;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++) dp[i][j][0]=dp[i][j][1]=0;
for(int i=1;i<=n;i++) G[i].clear();
for(int i=2;i<=n;i++){
int x;
cin>>x;
G[x].push_back(i),G[i].push_back(x);
}
for(int i=1;i<=n;i++) cin>>hp[i];
dfs(1,0);
for(int i=0;i<=n;i++) cout<<min(dp[1][i][0],dp[1][i][1])<<" ";
cout<<endl;
}
int main(){
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
Comments | NOTHING