牛客周赛 Round 69（A~E）

牛客周赛 Round 69

A 构造C的歪

思路

签到题，求出公差d，让最大的数加上公差d即可

code

	int a,b;cin >> a >> b;int k=max(a,b)-min(a,b);cout << max(a,b)+k; 

B 不要三句号的歪

思路

最优解法用scanf流直接读入中间的逗号和省略号

我的思路是用字符串截取，找到第一个逗号和最后一个逗号，截取字符串，再让字符串转化为long long类型
最后输出结果

code

void solve(){string s;cin >> s;string a;for(int i=0;i<s.size();++i){if(s[i]==','){a=s.substr(0,i);break;} }int k=s.rfind(',');string b=s.substr(k+1);int x=stoll(a)+1;int y=stoll(b);cout << y-x-1 << endl;return ;
}

C 仰望水面的歪

思路

在草稿纸把玩一下不难得出：一个点经过水面反射到达最终坐标经过的距离等于这个点到水面的距离
那么我们延长这个点到水面的距离，使得这两个线段相同，看下图：
牛客题解的图（太懒我就不画了QVQ）：

容易证明三角形CDE与三角形CEB全等，显然D点的横纵坐标与最终坐标B相同,竖坐标等于 $2\ast h-z$
因此只要在AD上面的点都满足经过水面反射会到达B点
对D点的坐标进行gcd处理，输出结果即可

code

void solve(){int n,h;cin >> n >> h;for(int i=1;i<=n;++i){int a,b,c;cin >> a >> b >> c;int z=2*h-c;int g=__gcd(__gcd(a,b),z);cout << a/g << " " << b/g << " " << z/g << endl;}return ;
}

D 小心火烛的歪

思路

考点：dfs

数据范围很小，直接纯暴力模拟所有情况即可
需要注意：空地可以堆放多个炸弹，有杂草的地方不能放任何炸弹
我们只需要判断能否将空地全部填上炸弹即可

code

const int N=10;
char a[N][N],b[N][N][N],v[N][N];
int cnt[N][N];
int sum=0;
vector<int> ans,c;
int n,m,q,r;
void dfs(int num){int f=1;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){if(v[i][j]=='0'){f=0;break;}}if(f){if(r==0){for(auto i : c) ans.push_back(i);}else{if(sum<ans.size()){while(!ans.empty()) ans.pop_back(); for(auto i : c) ans.push_back(i);}}r=1;return ;}for(int k=num;k<=q;++k){int flag=1;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){if(a[i][j]=='1' && b[k][i][j]=='1'){flag=0;break;}}if(flag){c.push_back(k);sum++;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){if(b[k][i][j]=='1'){cnt[i][j]++;v[i][j]='1';} }dfs(k+1);sum--;c.pop_back();for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){if(b[k][i][j]=='1'){cnt[i][j]--;if(cnt[i][j]==0) v[i][j]='0';} }}}
}
void solve(){cin >> n >> m >> q;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){cin >> a[i][j];v[i][j]=a[i][j];}for(int k=1;k<=q;++k){for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){cin >> b[k][i][j];}}dfs(1);if(r==0) cout << -1 << endl;else{cout << ans.size() << endl;for(auto i : ans) cout << i << " ";}return ;
}

E 喜欢切数组的红

思路

考点：前缀和

将数组a进行前缀和处理，另开一个数组b进行正数的前缀和处理
这时分2种情况考虑：

• 累加数组a中所有元素，如果不能被3整除，直接输出0（说明它不能被分为3个区域）
• 如果满足，在定义两个动态数组 $f,g$ ，遍历前缀和数组a
  当第一个区域满足 $a[i]==a[n]/3$ ，将下标存入f数组
  当第二个区域满足 $a[i]==a[n]/3\ast 2$ ，将下标存入g数组

双重循环遍历这些区域，如果划分之后的3块区域都含有正数，$ans++$
最后输出 $ans$

code

const int N=1e6+5;
int a[N],b[N];
void solve(){int n;cin >> n;for(int i=1;i<=n;++i){cin >> a[i];if(a[i]>0) b[i]++;a[i]+=a[i-1];b[i]+=b[i-1];}if(a[n]%3!=0){cout << 0 << endl;return ;}vector<int> f,g;for(int i=1;i<=n;++i){if(a[i]==a[n]/3) f.push_back(i);if(a[i]==a[n]/3*2) g.push_back(i);}int ans=0;for(auto i : f){if(b[i]==0) continue;for(auto j : g){if(b[j]-b[i]>0 && b[n]-b[j]>0) ans++;}}cout << ans << endl;return ;
}