AtCoder Beginner Contest 407(ABCDE)

A - Approximation

翻译：

        给你一个正整数 A 和一个正奇数 B。
        请输出与实数   的差最小的整数。
        可以证明，在约束条件下，这样的整数是唯一的。

思路：

        令。比较来判断答案。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int a,b;cin>>a>>b;int c = a/b;if (1.0*a/b-c<(c+1)-1.0*a/b){cout<<c<<endl;}else{cout<<c+1<<endl;}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();solve();return 0;
}

B - P(X or Y)

翻译：

        掷两颗骰子，每颗骰子都有六个面 1、2、3、4、5、6。求以下两个条件中至少有一个成立的概率：

• 两个结果之和至少为 X。
• 两个结果的绝对差至少为 Y。

        每个骰子的每个面的可能性相同，且两个骰子是独立的。

思路：

        遍历所有情况并判断条件是否成立。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int x,y;
bool check(int a,int b){return (a+b>=x || abs(a-b)>=y);
}
void solve(){cin>>x>>y;int cnt = 0;for (int i=1;i<=6;i++){for (int j=1;j<=6;j++){cnt+=check(i,j);}}cout<<1.0*cnt/36<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法cout<<fixed;// 四舍五入中间填保留几位小数，不填默认cout.precision(9);solve();return 0;
}

C - Security 2

翻译：

        在 AtCoder 公司的入口处，有一个特殊的密码输入装置。该设备由一个显示一个字符串的屏幕和两个按钮组成。

        让 t 是屏幕上显示的字符串。最初 t 是空字符串。按下按钮后，t 会发生如下变化：

• 按 A 按钮会在 t 的末尾添加 0。
• 按 B 按钮将 t 中的每个数字替换为下一个数字。t 中的每一位数字替换为下一位数字。1；9 之后的下一位数为 0。

        例如 t 为 1984，按下 A 按钮、 t 就变成了 19840；如果按下 B 按钮，t 就变成了 20951、 t 就会变成 20951。

        给您一个字符串 S. 从空字符串开始，按下 0 次或更多次按钮，直到 t 与 S. 求最少需要按多少次按钮。

思路：

        s从后往前判断，当前数位为 i 时，说明到最终答案的状态要在加0后按i次，而之前的值都要也按 i 次。再下一个数位以此类推。（模拟）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){string s;cin>>s;int ans = s.size(),cnt = 0;for (int i=s.size()-1;i>=0;i--){int now = s[i]-'0';int need = (10+(now-cnt)%10)%10;ans+=need;cnt+=need;}cout<<ans<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法cout<<fixed;// 四舍五入中间填保留几位小数，不填默认cout.precision(9);solve();return 0;
}

D - Domino Covering XOR

翻译：

        有一个 H 行 W 列的网格。让 (i,j) 表示位于 从上往下数第 i 行的单元格（1≤i≤H）和从左往下数第 j 列的单元格（1≤j≤W）。

        单元格 (i,j) (1≤i≤H,1≤j≤W) 上写有一个非负整数 A i,j。

        让我们在网格上放置零块或多块多米诺骨牌。一块多米诺骨牌覆盖两个相邻的单元格，即以下两对中的一对：

• 单元格 (i,j) 和 (i,j+1) 为 1≤i≤H，1≤j<W；
• 单元格 (i,j) 和 (i+1,j) 为 1≤i<H，1≤j≤W。

        任何单元格都不能被一块以上的骨牌覆盖。

        对于多米诺骨牌的摆放，其得分定义为写在未被任何多米诺骨牌覆盖的单元格中的所有整数的比特 XOR。

        求最大可能得分。

思路：

        数据量足够小，直接遍历所有情况(几块多米诺骨牌，每块多米诺骨牌的摆放方式)比较答案大小。（dfs）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){ll h,w;cin>>h>>w;vector<vector<ll>> maze(h,vector<ll>(w));ll now = 0,ans = 0;for (ll i=0;i<h;i++){for (ll j=0;j<w;j++){cin>>maze[i][j];now ^= maze[i][j];}}vector<vector<ll>> vis(h,vector<ll>(w,0));auto dfs = [&](auto&& dfs,ll cnt,ll x,ll y,ll now){if (cnt==0){ans = max(ans,now);return;}if (x==h-1 && y==w-1) return;// 不拿dfs(dfs,cnt,x+(y==w-1),(y+1)%w,now);// 拿if (vis[x][y]==0){vis[x][y] = 1;// 拿下if (x!=h-1 && vis[x+1][y]==0){vis[x+1][y] = 1;dfs(dfs,cnt-1,x+(y==w-1),(y+1)%w,now^maze[x][y]^maze[x+1][y]);vis[x+1][y] = 0;}// 拿右if (y!=w-1 && vis[x][y+1]==0){vis[x][y+1] = 1;dfs(dfs,cnt-1,x+(y==w-1),(y+1)%w,now^maze[x][y]^maze[x][y+1]);vis[x][y+1] = 0;}vis[x][y] = 0;}};for (int i=0;2*i<=h*w;i++){dfs(dfs,i,0,0,now);}cout<<ans<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法
//     cout<<fixed;// 四舍五入中间填保留几位小数，不填默认
//     cout.precision(9);solve();return 0;
}

E - Most Valuable Parentheses

翻译：

        给你一个长度为 2N 的非负整数序列 A=（A 1 ，...，A 2N ）。

        长度为 2N 的括号序列 s 的得分定义如下：

• 对于 s 的第 i 个字符为 ) 的每个位置 i，设 A i  为 为 0，然后求 A 的所有元素之和。

        求长度为 2N 的正确括号序列的最大可能得分。

        给你 T 个测试用例，请逐个求解。

思路：

        序列A的两端是可以确定状态的，之后自前向后同时取两个放入大根堆，并从中取出最大的值，作为符号（。此过程保证了左括号始终大于等于右括号。（堆，贪心）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){ll n;cin>>n;vector<ll> a(2*n);for (ll &i:a) cin>>i;ll ans = a[0];priority_queue<ll> pq;for (ll i=1;i<n;i++){pq.push(a[2*i-1]);pq.push(a[2*i]);ans+=pq.top();pq.pop();}cout<<ans<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法
//     cout<<fixed;// 四舍五入中间填保留几位小数，不填默认
//     cout.precision(9);ll t;cin>>t;while (t--) solve();return 0;
}

之后补题会在此增加题解。