A. Architecture
如果行最大值中的最大值和列最大值中的最大值不同的话，那么一定会产生矛盾，可以手模一个样例看看。
当满足行列最大值相同条件的时候，就可以判定了。
因为其余的地方一定可以构造出来符合条件的值，行列是很多的，填0就好了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n, m; cin >> n >> m;
int t1, t2;
t1 = t2 = 0;
for(int i = 1, x; i <= n; i++)
{
scanf("%d", &x);
t1 = max(t1, x);
}
for(int i = 1, x; i <= m; i++)
{
scanf("%d", &x);
t2 = max(t2, x);
}
if(t1 == t2) puts("possible");
else puts("impossible");
return 0;
}
B. Bracket Sequence
用栈模拟即可，注意要取模
const int N = 300000 + 5;
const int mod = 1e9 + 7;
ll st[N], top, cnt;
int n;
char op[20];
ll get(char *s){
int len = strlen(s);
ll x = 0;
for(int i=0;i<len;i++) x = x * 10 + s[i] - '0';
return x;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",op);
if(op[0] == '(') {
cnt ++;
st[++top] = -1;
continue;
}
else if(op[0] == ')'){
if(st[top] == -1) {
top --;
continue;
}
ll x = st[top];
while(top >= 2 && st[top-1] != -1){
if(cnt % 2 == 0)x = (st[top-1] + x)%mod;
else x = st[top-1] * x % mod;
top--;
}
cnt --;
top -= 2;
st[++top] = x;
}
else{
ll x = get(op);
st[++top] = x;
}
}
ll res = 0;
while(top) res = (res + st[top--]) % mod;
printf("%lld
", res);
return 0;
}
C. Canyon Crossing
二分一下最低高度，然后整个图变成了 n*m 个点，边权为0或1的图，第一排为起点，最后一排为终点，跑最短路即可，由于边权只有0和1，所以用双端队列维护即可
const int N = 1000 + 5;
#define mk make_pair
int n, m, k, a[N][N];
int d[N][N],c[N][N];
int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
pair<int,int> q[2000010];
bool check(int mid){
memset(d, 0x3f, sizeof d);
int l = 1000005,r = 1000004;
for(int j=1;j<=m;j++)q[++r] = mk(0,j), d[0][j] = 0;
while(l<=r){
auto t = q[l++];
int x = t.first, y = t.second;
for(int i=0;i<4;i++){
int nx = x + dx[i], ny = y + dy[i];
if(nx < 1 || nx > n || ny < 1 || ny > m)continue;
if(a[nx][ny] >= mid){
if(d[nx][ny] > d[x][y]){
d[nx][ny] = d[x][y];
q[--l] = mk(nx,ny);
}
}else{
if(d[nx][ny] > d[x][y] + 1){
d[nx][ny] = d[x][y] + 1;
q[++r] = mk(nx,ny);
}
}
}
}
for(int i=1;i<=m;i++)if(d[n][i] <= k) return true;
return false;
}
int main() {
scanf("%d%d%d",&n,&m,&k);
int l = inf, r = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
l = min(l, a[i][j]);
r = max(r, a[i][j]);
}
}
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid))l = mid;
else r = mid - 1;
}
printf("%d
",l);
return 0;
}
D. Deceptive Dice
(ans) 为 (i-1) 轮的期望，设 (t = lfloor ans floor) ，那么第 (i) 轮的期望是
[frac{t}{n} * ans + frac{sum_{t+1}^{n}i}{n}
]
前面的表示有 (t/n) 的概率小于等于ans，那么第 i 次就不再掷色子。后面的就是取 [i+1, n] 的期望
const int N = 100 + 5;
int n, m;
double ans;
int get(int x){return x*(x+1) / 2;}
int main() {
scanf("%d%d",&n,&m);
ans = 1.0 * get(n) / n;
for(int i=2;i<=m;i++){
int t = ans;
ans = 1.0 * t / n * ans + 1.0 * (get(n) - get(t)) / n;
}
printf("%.7f
",ans);
return 0;
}
E. Exits in Excess
这个题有个关键的性质在于无自环。
设两个集合(S,T)。
考虑一条边(<x,y>)，如果(x<y)，将这条边插入(S)；否则插入(T)。
输出边集大小较小的集合。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> t1, t2;
int n, m;
int main()
{
cin >> n >> m;
for(int i = 1, x, y; i <= m; i++)
{
scanf("%d%d", &x, &y);
if(x < y) t1.push_back(i);
else t2.push_back(i);
}
if(t1.size()>t2.size()) t1 = t2;
cout << t1.size() << endl;
for(auto x : t1)
printf("%d
", x);
return 0;
}
F. Floor Plan
int n;
int main() {
cin >> n;
int flag = false;
for(int i=2;i*i<=n;i++){
if(n % i == 0){
int res = n / i;
if((res + i)%2 == 0){
flag = true;
int a = (res + i) / 2;
int b = res - a;
printf("%d %d
",b, a);
break;
}
}
}
if(!flag) puts("impossible");
return 0;
}
G. Greetings!
const int N = 100000 + 5;
char s[N];
int main() {
cin >> s;
int n = strlen(s);
printf("h");
for(int i=0;i<2*(n-2);i++)printf("e");
printf("y");
return 0;
}
H. Hexagonal Rooks
从起点走两步走到终点，枚举中间的那个点，判断它与起点和终点是否可以一步达到即可，判断细节比较重要，把大于纵坐标大于 'f' 的对称往上翻即可，用几种case找找规律即可。
char x, x2;
int y, y2;
bool check(int x, int y, int x2, int y2){
if(x == x2 && y == y2) return false;
if(x == x2) return true;
if(x > 6) y += x - 6;
if(x2 > 6) y2 += x2 - 6;
if(y == y2 || y - x == y2 - x2) return true;
return false;
}
int main() {
cin >> x >> y >> x2 >> y2;
int res = 0;
for(int i=1;i<=11;i++){
int cnt = 11 - abs(6 - i);
for(int j=1;j<=cnt;j++){
if(check(i, j, x-'a'+1, y) && check(i, j, x2-'a'+1, y2)) res++;
}
}
cout << res << endl;
return 0;
}
I. Inquiry I
const int N = 1000000 + 5;
ll a[N], b[N], sa[N], sb[N];
int n;
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i] = a[i]*a[i];
ll res = 0;
for(int i=1;i<=n;i++) sa[i] = sa[i-1] + a[i], sb[i] = sb[i-1] + b[i];
for(int i=0;i<=n;i++){
res = max(res, sb[i] * (sa[n] - sa[i]));
}
printf("%lld
",res);
return 0;
}
K. Knapsack Packing
首先排个序，最小的一定是0（空集产生的和），然后次小的就是集合中最小的数了。之后每次找到一个新的数字（即最终答案集合中的数字），都用它与之前所有组合出来的数字进行求和，将这些新的数字填入到一个集合中，再接下来的扫描过程中，如果发现有该集合的数字，则一定不是答案集合中的数字，将其从集合中删除即可。
const int N = 300000 + 5;
int n, m, a[N];
multiset<int> st, tmp;
map<int,int> mp;
vector<int> res;
int main() {
scanf("%d",&n);
m = 1 << n;
for(int i=1;i<=m;i++)scanf("%d",&a[i]);
sort(a+1,a+1+m);
if(a[1] != 0){
puts("impossible");
return 0;
}
int cnt = 0;
for(int i=2;i<=m;i++){
if(mp[a[i]]){
mp[a[i]] --;
continue;
}else{
cnt ++;
res.push_back(a[i]);
for(auto x:st){
tmp.insert(x + a[i]);
}
for(auto x : tmp) {
st.insert(x);
mp[x] ++;
}
st.insert(a[i]);
tmp.clear();
}
if(cnt > n){
puts("impossible");
return 0;
}
}
sort(res.begin(),res.end());
for(auto x : res)printf("%d
",x);
return 0;
}
L. Lifeguards
将点按照坐标轴排序，找到中间的点，对于n的奇偶进行分别处理。
n 为奇数则构造一个几乎平行于y轴且通过中间点的直线，可以想到做这条直线的垂直平分线可以将所有点分成两半
n 为偶数则构造一个几乎平行于y轴且不通过中间点的直线，这样的直线的垂直平分线也同样会把所有点分成两半
const int N = 100000 + 5;
pair<ll,ll> a[N];
int n;
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].first, &a[i].second);
sort(a + 1, a + 1 + n);
int mid = (n + 1) / 2;
ll Len = 1000000000000ll;
ll x = a[mid].first, y = a[mid].second;
if(n & 1){
printf("%lld %lld
", x - Len, y-1);
printf("%lld %lld
", x + Len, y+1);
}else{
printf("%lld %lld
", x - Len, y);
printf("%lld %lld
", x + Len, y+1);
}
return 0;
}