2017-2018 ACM-ICPC Southeast USA Regional Contest (Div. 1)
前言
26号花四个小时练了一下，A了三题，太菜了QAQ
本文讲四题，剩下的题目如果能懂再说 _(:з」∠)_
关于训练
开头十多分钟，一直在看A、B题，直到看到有人A了i题，于是看了一下A掉这道签到题
转而看J题，感觉好像是DP，于是用DP思路写了一下AC
看到D题过的人比较多，于是看D，感觉很像POJ的滑雪，用DFS+DP交了一发TLE，想了一下好像复杂度的确爆炸，本来可以用线段树优化，但是担心爆内存，于是用了单调队列优化，结果写错了WA了一发 = =||，改完AC
然后就再也A不掉其他题目了 QAQ
Star Arrangements - Gym - 101617I
题意
给定星星数量，要求奇数行比偶数行摆放的数量一样或多1，求全部摆法
思路
签到题，不说了
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 10000 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
const ll MOD = 1000000007;
int main(){
int n;
while(~scanf("%d", &n)){
for(ll i = 2; i <= n && 2*i - 1 <= n; i++){
if(n%(2*i - 1) == 0 || n%(2*i - 1) == i){
printf("%lld %lld\n", i, i - 1);
}
if(n%(2*i) == 0 || n%(2*i) == i){
printf("%lld %lld\n", i, i);
}
}
}
}
Treasure Map Gym - 101617J
题意
给出n个点，m条边，每一条边需要花k天才能走完，第一天的时候这个人在点1，第i个点在第一天的时候有权值gi，每天减少di，最多减少到零，在不能相邻两天都待在同一个点的情况下，问这个人能得到的最大价值是多少
思路 —— DP
定义DP状态dp[u][j]为点u在第j天能获得的最大价值，则
dp[v][j + w] = max(dp[u][j] + max(0, g[v] - d[v]*(j + w)))
答案就在其中取最大
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1000 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
const ll MOD = 1000000007;
struct edge{
int v, nxt, w;
};
edge e[N << 1];
int head[N];
int tot;
int g[N], d[N];
ll dp[N][N];
inline void init(){
memset(head, -1, sizeof(head));
tot = 0;
}
inline void addEdge(int u, int v, int w){
e[tot] = edge{v, head[u], w};
head[u] = tot++;
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
init();
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++){
scanf("%d%d", &g[i], &d[i]);
}
while(m--){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
ll ans = g[1];
dp[1][0] = g[1];
for(int j = 0; j < N - 1; j++){
for(int u = 1; u <= n; u++){
if(dp[u][j]){
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
int w = e[i].w;
if(j + w >= N) continue;
dp[v][j + w] = max(dp[v][j + w], dp[u][j] + max(0, g[v] - d[v]*(j + w)));
ans = max(ans, dp[v][j + w]);
}
}
}
}
printf("%lld\n", ans);
}
}
Jumping Haybales - Gym - 101617D
题意
给定一幅图，要求从左上角走到右下角，而且只能够往右或往下走，一次可以走k步，但是不能够落在‘#’的点中，问最少步数
思路 —— 单调队列 + DP
定义DP状态为dp[i][j]为落到第(i,j)的最少步数，则
dp[i][j] = min(min(dp[i - k][j], dp[i - k + 1][j], ..., dp[i - 1][j]), min(dp[i][j - k], dp[i][j - k + 1], ..., dp[i][j - 1]))
但是要取出中间的最小值是比较麻烦的，如果选择用线段树的话容易爆内存，可以选择使用单调队列优化，毕竟这是定长RMQ问题了
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <deque>
using namespace std;
const int N = 2000 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
const ll MOD = 1000000007;
char G[N][N];
int d[N][N];
deque<pii> dqrow[N], dqcol[N];
int getD(int n, int k){
for(int i = 0; i < n; i++){
dqrow[i].clear();
dqcol[i].clear();
}
d[0][0] = 0;
dqrow[0].push_back(make_pair(0, 0));
dqcol[0].push_back(make_pair(0, 0));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == 0 && j == 0) continue;
d[i][j] = inf;
while(!dqrow[i].empty() && dqrow[i].front().second < j - k) dqrow[i].pop_front();
while(!dqcol[j].empty() && dqcol[j].front().second < i - k) dqcol[j].pop_front();
if(G[i][j] != '#' && !dqrow[i].empty()) d[i][j] = min(d[i][j], dqrow[i].front().first + 1);
if(G[i][j] != '#' && !dqcol[j].empty()) d[i][j] = min(d[i][j], dqcol[j].front().first + 1);
while(!dqrow[i].empty() && dqrow[i].back().first > d[i][j]) dqrow[i].pop_back();
dqrow[i].push_back(make_pair(d[i][j], j));
while(!dqcol[j].empty() && dqcol[j].back().first > d[i][j]) dqcol[j].pop_back();
dqcol[j].push_back(make_pair(d[i][j], i));
}
}
return d[n - 1][n - 1];
}
int main(){
int n, k;
while(~scanf("%d%d", &n, &k)){
for(int i = 0; i < n; i++){
scanf("%s", G[i]);
}
int ans = getD(n, k);
printf("%d\n", ans == inf ? -1 : ans);
}
}
Security Badges - Gym - 101617H
题意
给定n个点m条边，通过每个点都有一个范围[l,r]，问从源点到汇点有多少数字是可以通过的
思路 —— 离散化 + 暴力
看了一下题解 orz
把区间端点提出来离散化，然后直接枚举左右端点即可，因为经过离散化之后原来的区间变成了小区间，所以答案一定是某些区间的并集
另外为了方便合并，离散化时采用左闭右开的区间形式，枚举的时候右端减1即可
最后枚举区间，如果ok就累加区间长度作为答案
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000 + 15;
const int M = 5000 + 15;
const int inf = 0x3f3f3f3f;
struct edge{
int v, nxt, l, r;
};
edge e[M];
int head[N];
int tot;
int a[M << 1], pp;
bool used[N];
inline void init(){
memset(head, -1, sizeof(head));
tot = pp = 0;
}
inline void addEdge(int u, int v, int l, int r){
e[tot] = edge{v, head[u], l, r};
head[u] = tot++;
}
bool dfs(int u, int des, int l, int r){
if(u == des) return true;
used[u] = true;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(!used[v] && e[i].l <= l && r <= e[i].r && dfs(v, des, l, r)){
//used[u] = false;
return true;
}
}
//used[u] = false;
return false;
}
int main(){
int n, m, k;
while(~scanf("%d%d%d", &n, &m, &k)){
init();
int src, des;
scanf("%d%d", &src, &des);
while(m--){
int u, v, l, r;
scanf("%d%d%d%d", &u, &v, &l, &r);
addEdge(u, v, l, r);
a[pp++] = l;
a[pp++] = r + 1;
}
sort(a, a + pp);
pp = unique(a, a + pp) - a;
int ans = 0;
for(int i = 1; i < pp; i++){
memset(used, false, sizeof(used));
if(dfs(src, des, a[i - 1], a[i] - 1)){
ans += (a[i] - a[i - 1]);
}
}
printf("%d\n", ans);
}
}
