这是本人在离开了OI，上了大学后参加的第一场算法竞赛，由于出题方向与赛制与之前参加过的比赛大不相同，所以呢这次很遗憾的就打铁了。2021年回来复盘发现很多题其实并不难只是当时想的太偏了，回来写篇题解吧
B. Mine Sweeper II
题目链接：https://ac.nowcoder.com/acm/contest/9925/B
这道题大致意思是说给你两幅扫雷的图，每个空白的地方上面有个数字，这个数字等于周围一圈雷的数量，最后问需要怎样变换能使得第二张图数字之和等于第一张图数字之和，变换次数不能超过nm/2。我们先来验证一条结论，一张扫雷图里面，把空白全变成雷，雷全变成空白，数字之和不变。下面有一个简单的证明方法，一个空白的周围有k个雷，把空白变成雷数字之和贡献-k，然后把k个雷全变成空白贡献又加k，总贡献为0，数字之和不变。这回容易了，先去统计图一和图二有几处不同，如果数量小于nm/2，那我们就直接输出图一原图，反之我们选择输出图一的取反图，图二和取反图的不同之处一定会小于nm/2。至于-1嘛，唬人用的，贴代码！
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s1[1005][1005],s2[1005][1005];
void solve(){
int n,m,cnt=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",s1[i]+1);
for(int i=1;i<=n;i++)
scanf("%s",s2[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s1[i][j]=(s1[i][j]=='X'?'.':'X');
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cnt+=(s1[i][j]!=s2[i][j]);
if(cnt>n*m/2){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
if(s1[i][j]=='.') printf("X");
else printf(".");
printf("\n");
}
return;
}
for(int i=1;i<=n;i++)
printf("%s\n",s1[i]+1);
}
int main(){
solve();
return 0;
}
C.Sum of log
题目链接：https://ac.nowcoder.com/acm/contest/9925/C
一道数位dp的题，奈何本人当时还没有写过数位dp的题，愣是没做出来这道题。这道题有提到按位和，所以必定是一个二进制下的数位dp,维护dp[now][f1][f2],now表示的是当前为第几位，f1表示的是第一个数字是否被卡位，f2表示第二个数字是否被卡位。如果两个数字按位和之后等于0，那么二者相加，在二进制下必然不会进位，二进制下有多少位，以二为底的对数就是几。不多bb贴代码。
#include <bits/stdc++.h>
#define ll long long
const int MOD=1e9+7;
using namespace std;
ll dp[50][2][2][2],a[50],b[50],cnt1,cnt2,cnt;
int dfs(int now,bool f1,bool f2,bool fir){
if(!now) return 1;
if(dp[now][f1][f2][fir]!=-1) return dp[now][f1][f2][fir];
int up1=f1?a[now]:1;
int up2=f2?b[now]:1;
ll tmp=0;
for(int i=0;i<=up1;i++)
for(int j=0;j<=up2;j++){
if(!(i|j)&&fir) continue;
if(i&j) continue;
tmp+=dfs(now-1,f1&&i==up1,f2&&j==up2,fir&0)%MOD;
tmp%=MOD;
}
return dp[now][f1][f2][fir]=tmp;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
cnt1=cnt2=0;
memset(dp,-1,sizeof(dp));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int x,y;
scanf("%d%d",&x,&y);
while(x){
a[++cnt1]=x&1;
x>>=1;
}
while(y){
b[++cnt2]=y&1;
y>>=1;
}
ll ans=0;
int cnt=max(cnt1,cnt2);
for(int i=cnt;i>=1;i--)
dfs(i,i>=cnt1,i>=cnt2,1);
for(int i=1;i<=cnt;i++){
for(int j=0;j<=1;j++)
for(int k=0;k<=1;k++){
if(dp[i][j][k][1]==-1) continue;
ans+=dp[i][j][k][1]*i;
ans%=MOD;
}
}
printf("%lld\n",ans);
}
return 0;
}
D.Walker
题目链接：https://ac.nowcoder.com/acm/contest/9925/D
考虑几种情况，两人对穿而行，总时间为两人各需要行走时间的最大值，另一种是让其中一个人走完全程，需要时间为各需要时间的最小值，第三种情况是让他俩各自走属于自己的路最后相遇在中间，我们可以选择二分他俩的会合点
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
void solve(){
double n,p1,p2,v1,v2;
scanf("%lf%lf%lf%lf%lf",&n,&p1,&v1,&p2,&v2);
if(p1>p2){swap(p1,p2);swap(v1,v2);}
p2=n-p2;
double ans=max((n-p1)/v1,(n-p2)/v2);
//printf("%f\n",ans);
ans=min(ans,min((n+min(p1,n-p1))/v1,(n+min(p2,n-p2))/v2));
//printf("%f\n",ans);
double l=p1,r=n-p2;
double t1,t2;
while(r-l>=1e-10){
double mid=(l+r)/2;
double s1=mid+min(p1,mid-p1),s2=n-mid+min(n-mid-p2,p2);
t1=s1/v1,t2=s2/v2;
ans=min(ans,max(t1,t2));
if(t1<t2)
l=mid;
else
r=mid;
}
printf("%.10f\n",ans);
}
int main(){
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}
G. Fibonacci
题目链接：https://ac.nowcoder.com/acm/contest/9925/G
这题我没去推结论打标找规律来着
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
ll n;
int main(){
scanf("%lld",&n);
if(n<3){
printf("0");
return 0;
}
ll a=(n-3)/3;
ll b=(n-3)%3;
long long ans=2+(5*a*a+9*a)/2;
ans+=b*a+b;
printf("%lld",ans);
return 0;
}
I.Sky Garden
题目链接：https://ac.nowcoder.com/acm/contest/9925/I
这题大至就是计算点到点之间最短距离之和，具体方案是有两种路线，一种是在圆上走，另一种是往里面走一步，再在圆上走，这听起来很像动规是不是，但其实并不用这么麻烦，可以选择以为在一个平分的圆上，可以很容易的直接计算出往里面走更近还是在圆上更近，这里面有个容斥原理倒是有点没推出来
#include <bits/stdc++.h>
using namespace std;
const double PI=3.14159265358;
double ans=0;
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=n;i>=1;i--){
double f=PI*i*1.0/m;
int out=(2*i)/f;
int in=2*m-2*out-1;
double num=(out+1)*out*f;
num+=in*2*i;
num*=m;
for(int j=i-1;j>=1;j--){
double tmp=0;
tmp+=(i-j)*2*m;
double f2=PI*j/m;
tmp+=in*2*j;
tmp+=(out+1)*out*f2;
tmp*=2*m;
num+=tmp;
}
ans+=num;
}
if(m != 1) ans += 1.0 * m * (1 + n) * n;//只有一条线，圆心就没有交点了
printf("%.10f",ans);
return 0;
}
//(m*m-m)Πr+m*r
M. Gitignore
题目链接：https://ac.nowcoder.com/acm/contest/9925/M
现场写了个超级恶心的大模拟，然而写崩了，从此立志，再写数组版数据结构我就是狗！本人写了个树形结构，贴一个改进后的代码吧。不过后来看有一些提交特别简短实在是佩服
#include <bits/stdc++.h>
using namespace std;
struct Tree{
string name;
vector<Tree*>v;
bool ignore;
};
int dfs(Tree* now){
if(now->ignore==1)
return 1;
int ans=0;
for(int i=0;i<now->v.size();i++){
ans+=dfs(now->v[i]);
}
return ans;
}
void Solve(Tree* root){
int n,m;
scanf("%d%d",&n,&m);
for(int k=1;k<=n;k++){
Tree* now=root;
string s;
cin>>s;
string tmp;
for(int i=0;i<s.size();i++){
tmp+=s[i];
if(s[i]=='/'){
bool flag=0;
for(int j=0;j<now->v.size();j++){
if(tmp==now->v[j]->name){
flag=1;
now=now->v[j];
break;
}
}
if(!flag){
Tree* nxt=new Tree;
nxt->name=tmp;
nxt->ignore=1;
now->v.push_back(nxt);
now=nxt;
}
tmp.clear();
}
}
Tree* nxt=new Tree;
nxt->name=tmp,nxt->ignore=1;
now->v.push_back(nxt);
}
for(int k=1;k<=m;k++){
Tree* now=root;
string s;
cin>>s;
string tmp;
for(int i=0;i<s.size();i++){
tmp+=s[i];
if(s[i]=='/'){
bool flag=0;
for(int j=0;j<now->v.size();j++){
if(tmp==now->v[j]->name){
flag=1;
now=now->v[j];
break;
}
}
if(!flag){
Tree* nxt=new Tree;
nxt->name=tmp;
nxt->ignore=0;
now->v.push_back(nxt);
now=nxt;
}
now->ignore=0;
tmp.clear();
}
}
Tree* nxt=new Tree;
nxt->name=tmp,nxt->ignore=0;
now->v.push_back(nxt);
}
cout<<dfs(root)<<endl;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
Tree* root=new Tree;
root->ignore=0;
Solve(root);
}
return 0;
}
Comments | NOTHING