2020计蒜之道 预赛第一场 A、B
链接：https://www.jisuanke.com/contest/11344/challenges
A. 五子棋
枚举每个空格点的位置，然后判水平垂直以及两条对角线即可。判的时候可以沿那个方向往两边走，有连续棋子多于4个的话就获胜。
#include <bits/stdc++.h>
using namespace std;
int n = 24;
char mmap[30][30];
char go;
struct Point
{
int x, y;
};
vector<Point> v;
bool tran(int x, int y)
{
int cnt = 0, nx = x, ny = y - 1;
while(ny >= 0 && mmap[nx][ny] == go)
{
cnt++;
ny--;
}
ny = y + 1;
while(ny <= n && mmap[nx][ny] == go)
{
cnt++;
ny++;
}
if(cnt >= 4) return 1;
else return 0;
}
bool vertical(int x, int y)
{
int cnt = 0, nx = x - 1, ny = y;
while(nx >= 0 && mmap[nx][ny] == go)
{
cnt++;
nx--;
}
nx = x + 1;
while(nx <= n && mmap[nx][ny] == go)
{
cnt++;
nx++;
}
if(cnt >= 4) return 1;
else return 0;
}
bool MainDiagonal(int x, int y)
{
int cnt = 0, nx = x - 1, ny = y - 1;
while(nx >= 0 && ny >= 0 && mmap[nx][ny] == go)
{
cnt++;
nx--;
ny--;
}
nx = x + 1, ny = y + 1;
while(nx <= n && ny <= n && mmap[nx][ny] == go)
{
cnt++;
nx++;
ny++;
}
if(cnt >= 4) return 1;
else return 0;
}
bool SubDiagonal(int x, int y)
{
int cnt = 0, nx = x - 1, ny = y + 1;
while(nx >= 0 && ny <= n && mmap[nx][ny] == go)
{
cnt++;
nx--;
ny++;
}
nx = x + 1, ny = y - 1;
while(nx <= n && ny >= 0 && mmap[nx][ny] == go)
{
cnt++;
nx++;
ny--;
}
cout << cnt << endl;
if(cnt >= 4) return 1;
else return 0;
}
int main()
{
for(int i = 0; i < 25; i++)
{
scanf("%s", mmap[i]);
}
int w = 0, b = 0;
for(int i = 0; i < 25; i++)
{
for(int j = 0; j < 25; j++)
{
if(mmap[i][j] == 'o') w++;
else if(mmap[i][j] == 'x') b++;
}
}
if(w == b)//轮到黑棋走
{
go = 'x';
}
else go = 'o';
for(int i = 0; i < 25; i++)
{
for(int j = 0; j < 25; j++)
{
if(mmap[i][j] == '.')
{
if(tran(i, j) || vertical(i, j) || MainDiagonal(i, j) || SubDiagonal(i, j))
{
v.push_back({i, j});
}
}
}
}
if(!v.size()) cout << "tie" << endl;
else
for(int i = 0; i < v.size(); i++) cout << v[i].x << ' ' << v[i].y << endl;
return 0;
}
B. 染色（简单）
没在区间的直接染w和b较大的那个颜色，对于每个区间，由于彼此互不相交，直接比较“染同一个颜色然后获得bouns”以及“每个元素染w和b较大那个”然后取最大值累加到答案即可。
#include <bits/stdc++.h>
#define int long long//!!!!!
using namespace std;
int n, m, w[300005], b[300005], t[300005], l[300005], r[300005], c[300005];
bool seg[300005];
long long ans = 0;
signed main()
{
memset(seg, 0, sizeof(seg));
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> b[i];
for(int i = 1; i <= n; i++) cin >> w[i];
for(int i = 1; i <= m; i++)
{
cin >> t[i] >> l[i] >> r[i] >> c[i];
for(int j = l[i]; j <= r[i]; j++) seg[j] = 1;//在区间
}
for(int i = 1; i <= n; i++)
{
if(!seg[i]) ans += max(b[i], w[i]);
}
for(int i = 1; i <= m; i++)
{
int mmax = 0, black = 0, white = 0;
for(int j = l[i]; j <= r[i]; j++)
{
black += b[j];
white += w[j];
mmax += max(b[j], w[j]);
}
if(t[i] == 1)
{
ans += max(c[i] + black, mmax);
}
else
{
ans += max(c[i] + white, mmax);
}
}
cout << ans << endl;
}