标签：std int double DAY1 ny 补题 using dp

说句闲话：研究补题最好的方式是

补完AK了，祝你们成功（滑稽

此文章仅作为补题，题解等我理解完掉重新写。

比赛情况

不可饶恕的错误（滑稽

赛时第一题看错题意，导致明明可以做掉的内容爆了，T2考虑到了正解，可一直在推式子和打表中间晃荡，遗憾。T3很好笑，没有删除调试语句，赛后删了重交过到了30pts，正解DP我觉得30够了。T4成功骗到了样例分，赛后重看范围发现还是挂掉了本来很好想的部分分。

算了一下，不挂的话是可以打150以上的（爆哭

解题报告

交替出场(alter)

非常好想的思路，可惜读错题，将01字符串交替看作只能与上一个不同的字符串，加上了可爱的自己本身，然后成功爆掉。

其实正解赛时就该想到了，就是2层循环暴力跑一下，加一个小优化，当后面配不了就 break 掉。

跟我一起念，Cherry真屑（

可见读题的重要性。

正解：

#include <iostream>
using namespace std;
int main() {
    string s;
    cin >> s;
    int len = s.size(); 
    int cnt = 0;
    for(int i = 0; i < len; i ++) { // 字符串从0开始
        cnt ++; 
        for(int j = i + 1; j < len; j ++) {
            if(s[j] != s[j - 1]) cnt ++;
            else break; // 不加是不可以的，因为只要“交替” 的字符串(broken)
        }
    }
    cout << cnt;
    return 0;
}

翻翻转转(filp)

错误原因是一直考虑数学推法（可能与我近几天爆切数学题有关，上来就搞式子，搞了1h左右没跑出来，心态崩掉。

正解在推式子的时候想到过，并且观察到是对称的，但对打表和数学执念太深。以后30min推不出来的思路直接弃掉。不要把优势搞错了。

很神奇的是输出 1 有20pts，0 有10pts，x%2 有10pts。

但没想到这些就很屑。

正解最关键的是想到二分的处理，也就是取反对称，很明显在赛时推出来了。

不过老师说可以根据时间复杂度看算法倒是很神奇的思路，记下了。

扔一下正解。

#include <iostream>
using namespace std;
int x;
void fun(int l, int r, int p) {
    if(l == x && r == x) {
        cout << (1 == p) << endl;
        return;
    }
    int mid = (l + r) / 2;
    if(x <= mid) {
        fun(l, mid, p);
    } else {
        fun(mid + 1, r, ~p);
    }
}
int main() {
    int t;
    cin >> t;
    while(t --) {
       cin >> x;
       fun(1,1 << 30, 1);
    }
    return 0;
} 
//#include <iostream>
//using namespace std;
//int main() {
//    int t;
//    cin >> t;
//    while(t --) {
//        cout << 0 << endl;
//    }
//    return 0;
//}

讲几个小处理。

fun(1,1 << 30, 1); 这里没有要求我们的字符串长度,所以自己构造即可。范围是 \(10^{9}\) 的一半，int足够了。
(1 == p) 这个很巧妙啊，如果p是1输出1，也很好理解，当然直接if也可以的。
fun(mid + 1, r, ~p); 普通取反，但取反改成取相反数也是可以的，很神奇。

总之，T2没有场切，屑。

方格取数(square)

很有意思的一道题。

赛时一眼搜索，然后想到会爆掉，罚坐5min想dp，可惜没推出来（果然屑。转头敲搜索。

为什么不直接写搜索是因为我搜索不太好，甚至不如dp。

但很好的是拿到30pts。

笑点解析：忘删调试语句以及注释掉的 freopen 导致保灵。

放30的搜索：

#include <iostream>
using namespace std;
int a[210][210];
int vis[210][210];
int ans = 0, sum = -0x3f3f3f3f;
int n, m, k;
bool flag = 0;
void dfs(int x,int y,int step1,int step2) {
	if(!(x >= 1 && x <= n && y >= 1 && y <= m && step1 < k && step2 < k && vis[x][y])) {
		cout << "No Answer!";
		flag = 1;
		return;
	}
	if(!(x >= 1 && x <= n && y >= 1 && y <= m && step1 < k && step2 < k && !vis[x][y])) {
		sum = max(ans, sum);
		return; 
	}
	vis[x][y] = 1;
	ans += a[x][y];
	dfs(x, y + 1, step1 + 1, step2);
	dfs(x + 1, y, step1, step2 + 1);
}
int main() {
//	freopen("square.in","r",stdin);
//	freopen("square.out","w",stdout);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) {
		    cin >> a[i][j];
		}
	}
	dfs(1,1,0,0); 
	if(flag == 0) cout << sum;
	else if(flag != 1) cout << "Bad square!";
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

很有意思的是最不相信得分的有最高的分。

果然前面题还是要好好读一下的，不然掉分实参。

正解是一个多维dp，跑几次循环可做。思路比较麻烦到时候扔题解里。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 205; // 讲个笑话，一开始只能开201
int a[N][N];
int dx[] = {0,1};
int dy[] = {1,0};
ll dp[N][N][N][2];
ll ans = -1e18;
int main() {
    int n,m,k;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            cin >> a[i][j];
        }
    }
    memset(dp, -0x3f, sizeof dp);
    dp[1][1][0][0] = dp[1][1][0][1] = a[1][1];
    for(int x = 1; x <= n; x ++) {
        for(int y = 1; y <= m; y ++) {
            for(int l = 0; l < k; l ++) {
                for(int d = 0; d <= 1; d ++) {
                    for(int nd = 0; nd <= 1; nd ++) {
                        int nx = x + dx[nd];
                        int ny = y + dy[nd];
                        if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
                        if(d != nd) dp[nx][ny][1][nd] = max(dp[nx][ny][1][nd], dp[x][y][l][d] + a[nx][ny]);
                        else if(l < k - 1) dp[nx][ny][l + 1][nd] = max(dp[nx][ny][l + 1][nd], dp[x][y][l][d] + a[nx][ny]);
                    }
                }
            }
        }
    }
    for(int l = 0; l < k; l ++) {
        for(int d = 0; d <= 1; d ++) {
            ans = max(ans, (ll)dp[n][m][l][d]);
        }
    }
    if(ans == -1e18) cout << "No Answer!";
    else cout << ans;
	return 0;
}

老师跟我们说之前N只能开201，为了考验我们的实力，蚌。似乎现在改掉了。

输出 “No Answer!” 可以拿20pts，不可以总司令再现。

圆圆中的方方(round)

数学好题。老师讲红温掉开窗通风，很好。

赛后看题发现60pts是可做的，剩下的没学过。勾股定理和圆面积全部可做，加上样例就60pts了。

好歹是赛时5min搞的20pts，直接输出样例就难崩。

我的代码就是直接输出的样例，所以不放了。

正解：

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1), eps = 1e-6;
double n, m, x, y, r;
double calc(double n, double m, double r) {
	if(n > m) swap(n, m); // 方便后续处理，并且保证m比n大
	if(n < eps || m < eps) return 0;
	if(r <= n) return 0.25 * pi * r * r; //  正好截掉圆的四分之一角的情况
	else if(r <= m) {
		double tt = sqrt(r * r - n * n);
		double res = n * tt / 2.0;
		double ang = pi / 2 - acos(n / r);
		res += ang / 2 * r * r;
		return res;
	} else if(r <= sqrt(n * n + m * m)) {
		double t1 = sqrt(r * r - n * n);
		double t2 = sqrt(r * r - m * m);
		double res = n * t1 / 2.0 + m * t2 / 2.0;double ang = pi / 2 - acos(n / r) - acos(m / r);
		res += ang / 2 * r * r;
		return res;
	} else return n * m;
}
int main() {
	double n, m, x, y, r;
	cin >> n >> m >> x >> y >> r;
	cout << fixed << setprecision(10) << calc(x, y, r) + calc(x, m - y,r) + calc(n - x, y, r) + calc(n - x, m - y,r)<< endl;
	return 0;
}

没什么好讲的，思路会扔题解的（应该会的吧

总结

很差的一场模拟。

先是T1读错题，再是T2式子假掉，T3忘删调试，T4题目没读完。

预计分数应该在150的，可挂掉了很多很多。

一定一定记住删调试啊QAQ。

现在再找补什么也来不及了，只能说是场上心态以及做题方法很重要，能拿到多少算多少，数据范围多看看。

听说T3爆搜可以50pts？果然屑。

\(THANKS\)

标签：std,int,double,DAY1,ny,补题,using,dp
From： https://www.cnblogs.com/Cherry929/p/18443354

DAY1-补题