A
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N = 1e3 + 10;
int n, m;
int g[N][N];
int x, y, maxv;
int area;
int get(int x, int y)
{
return max(max( x * y , (n - x + 1) * y) , max( (n - x + 1) * (m - y + 1) , (m - y + 1) * x));
}
void solve()
{
cin >> n >> m;
area = 0 , maxv = -1e18;
for(int i = 1 ; i <= n ; i ++ )
for(int j = 1 ; j <= m ; j ++ )
{
int x;
cin >> x;
if(x > maxv)
{
maxv = x;
area = get(i, j);
}
else if(x == maxv && get(i, j) < area)
{
maxv = x , area = get(i, j);
}
}
cout << area << endl;
}
signed main()
{
int T;
cin >> T;
while(T -- ) solve();
return 0;
}
B
核心思路
其实像这种博弈论的题目我们应该首先就从n的奇偶性讨论。这里有一个很重要的性质：当n为偶数的时候就是其实这两个人分的石子堆是确定了的。
- n为奇数：这个很显然只要Mike刚开始把第一堆拿了，那么就肯定是joe输了
- n为偶数：首先我们可以贪心的考虑，每个人都不想输，所以每个人都尽量少拿石子：也就是每次只拿一个。所以看最少那堆石子花落谁家就好了。
// Problem: B. Circle Game
// Contest: Codeforces - Codeforces Round #801 (Div. 2) and EPIC Institute of Technology Round
// URL: https://codeforces.com/contest/1695/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
void solve()
{
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
if(n%2==1)
{
cout<<"Mike"<<endl;
return;
}
int smallest=0;
for(int i=0;i<n;i++)
{
if(a[i]<a[smallest])
smallest=i;
}
if(smallest%2==0)
cout<<"Joe\n";
else
cout<<"Mike\n";
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
C
核心思路
首先我们应该分析我们到达终点需要走多少步，这个还是比较容易分析出来的。那就是n+m-2步。而我们想要出现0.我们会发现我们走奇数步是完全不可能出现的，所以最终的答案肯定是偶数步。
挖掘出来这个性质就比较好做了：方格里面只有-1和1，所以我们走两步肯定只有-2 0 2这三种取值。
所以我们可以先预处理出来走到终点的最大值和最小值，这个使用dp就好了。然后判断0在不在这个范围了。
还有一点就是如果我们的最大值或者是最小值是奇数的话，由上面的分析可知道这一定走不到0的。
// Problem: C. Zero Path
// Contest: Codeforces - Codeforces Round #801 (Div. 2) and EPIC Institute of Technology Round
// URL: https://codeforces.com/contest/1695/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
const int N=1e3+10;
int g[N][N],maxn[N][N],minn[N][N];
void solve()
{
int n,m;
cin>>n>>m;
//不需要memset。要不然会tle。
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>g[i][j];
}
maxn[0][0]=g[0][0];
minn[0][0]=g[0][0];
for(int i=1;i<n;i++)
maxn[i][0]=minn[i][0]=maxn[i-1][0]+g[i][0];
for(int i=1;i<m;i++)
maxn[0][i]=minn[0][i]=maxn[0][i-1]+g[0][i];
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
{
minn[i][j]=min(minn[i-1][j],minn[i][j-1])+g[i][j];
maxn[i][j]=max(maxn[i-1][j],maxn[i][j-1])+g[i][j];
}
}
if(maxn[n-1][m-1]%2||minn[n-1][m-1]>0||maxn[n-1][m-1]<0||minn[n-1][m-1]%2)
{
NO;
}
else
{
YES;
}
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
D
题意
就是我们可以有k次询问，我们知道其他的点和k个点的距离。问我们最少询问多少次，可以确定每一个点的位置。
核心思路
easy：
首先我们需要知道的就是我们既然要确定以u为根的节点，那么就肯定需要把他的子树v全都确定了。并且如果有x个子树的答案是0，那我们就还需要加上x-1.因为我们最多只可以有1个节点没有确定。
hard：
我们需要优化时间复杂度，因为easy版本的我们需要做n次dfs，所以时间复杂度就是\(O(n^2)\).我们可以从每个点的出度来优化。因为只要有子节点的出度小于3，那么他就肯定是一条链，而链我们只需要取他的任意端点就可以确定了。
// Problem: D1. Tree Queries (Easy Version)
// Contest: Codeforces - Codeforces Round #801 (Div. 2) and EPIC Institute of Technology Round
// URL: https://codeforces.com/contest/1695/problem/D1?mobile=true
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
const int N=1e6+10;
vector<int> tree[N];
int dfs(int u,int fa)
{
int sum=0,z=0;
for(auto v:tree[u])
{
if(v!=fa)
{
int x=dfs(v,u);
sum+=x;
if(!x)
z++;
}
}
return sum+max(z-1,1LL*0);
}
void solve()
{
int n;
cin>>n;
int ans=n;
int m=n;
m--;
while(m--)
{
int u,v;
cin>>u>>v;
tree[u].push_back(v);
tree[v].push_back(u);
}
int max_dep=0;
for(int i=1;i<=n;i++)
{
max_dep=max(max_dep,(int)tree[i].size());
}
if(max_dep==0)
{
cout<<0<<endl;
}
else if(max_dep<3)
{
cout<<1<<endl;
}
else
{
for(int i=1;i<=n;i++)
{
if(tree[i].size()>=3)
{
cout<<dfs(i,i)<<endl;
break;
}
}
}
for(int i=1;i<=n;i++)
tree[i].clear();
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}