题集链接

代码

#include
#define endl "\n"
using namespace std;
typedef long long ll;
const int N = 1e6;
void solve()
{
ll mis = -1e10;
int a, b, n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { ll sa; cin >> sa;
if (sa > mis)
{
mis = sa;
a = i;
b = j;
}
}

int x = max(a, n - a + 1);  
int y = max(b, m - b + 1);  
cout << x \* y << endl;  

}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}

题意

有若干堆石子围成一个圆,第一个选手从第一堆开始取走任意个,然后第二个选手从前一个选手取的后一堆取走任意个,先不能取的输,谁会赢?

分析

如果石子有奇数堆那么先手必胜,因为先手可以一直全部取完,这样后手取到第一堆的时候就没有石子可取了.

如果石子有偶数堆,那么先手只能取奇数堆的石子,后手只能取偶数堆的石子,所以最优策略是每次少取,也就是每次取一个.所以如果只需比较奇数堆和偶数堆的最小值即可,如果最小值相等,最小值在前的必败.

代码

#include
#define endl "\n"
using namespace std;
typedef long long ll;
const int N = 1e6;
void solve()
{
int n;
cin >> n;
int s[n + 1];
for (int i = 1; i <= n; i++) cin >> s[i];
if (n % 2 == 1)
{
cout << "Mike\n"; return; } int s1 = 100, s2 = 100; int m1 = 1e9 + 23, m2 = 1e9 + 23; for (int i = 1; i <= n; i = i + 2) if (m1 > s[i])
{
m1 = s[i];
s1 = i;
}
else if (m1 == s[i] && s1 > i)
s1 = i;
for (int i = 2; i <= n; i = i + 2) if (m2 > s[i])
{
m2 = s[i];
s2 = i;
}
else if (m2 == s[i] && s2 > i)
s2 = i;
if (m2 > m1)
cout << "Joe\n"; else if (m2 == m1 && s2 > s1)
cout << "Joe\n"; else cout << "Mike\n"; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t; cin >> t;
while (t--)
{
solve();
}
return 0;
}

题意

给出一个权值只有 +1 和 -1 的矩阵,只能往下或者往右走,问是否能从左上走到右下使得路径之和为 0.

分析

首先如果 n+m 为偶数,那么路径和一定是奇数,所以一定走不到.

否则我们可以用两次 dp 分别求出左上走到右下路径的最大值和最小值,如果0在最大值和最小值之间说明存在这样的路径.

简易证明，因为 n+m 为奇数那么最后得到的值一定为偶数，每次微调会导致结果差2，因次只要0在最大值和最小值之间就可以通过微调得到.

比赛时证明不必要非常严谨，需要一点直觉猜测，有时候可以蒙一下.

代码

#include
#define endl "\n"
using namespace std;
typedef long long ll;
const int N = 1e3 + 233;
int dp1[N][N]; //最大
int dp2[N][N]; //最小
void solve()
{
int n, m;
cin >> n >> m;
int s[n + 1][m + 1];

for (int i = 1; i <= n; i++)  
    for (int j = 1; j <= m; j++)  
        cin >> s\[i\]\[j\];  
if ((n + m) % 2 == 0)  
{  
    cout << "NO\\n";  
    return;  
}  
for (int i = 1; i <= n; i++)  
    for (int j = 1; j <= m; j++)  
    {  
        if (i == 1)  
        {  
            dp1\[i\]\[j\] = s\[i\]\[j\] + dp1\[i\]\[j - 1\];  
            dp2\[i\]\[j\] = s\[i\]\[j\] + dp2\[i\]\[j - 1\];  
        }  
        if (j == 1)  
        {  
            dp1\[i\]\[j\] = s\[i\]\[j\] + dp1\[i - 1\]\[j\];  
            dp2\[i\]\[j\] = s\[i\]\[j\] + dp2\[i - 1\]\[j\];  
        }  
        if (i != 1 && j != 1)  
        {  
            dp1\[i\]\[j\] = s\[i\]\[j\] + max(dp1\[i\]\[j - 1\], dp1\[i - 1\]\[j\]);  
            dp2\[i\]\[j\] = s\[i\]\[j\] + min(dp2\[i\]\[j - 1\], dp2\[i - 1\]\[j\]);  
        }  
    }  
if (dp1\[n\]\[m\] >= 0 && dp2\[n\]\[m\] <= 0)  
    cout << "YES\\n";  
else  
    cout << "NO\\n";  

}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}