2018ICPC横滨区域赛

A. Digits Are Not Just Characters

 

模拟

直接把所有字母处理成数字，相邻数字都合并成一个数字，再逐位比较。

注意数字优先级始终比字母大，所以字母都加上INF

#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e4 + 5;
int n;
vector<string>a;
vector<ll>vc[1010];
string s;
bool cmp(int x, int y) {//x<y true
	int i = 0, j = 0;
	while (i < vc[x].size() && j < vc[y].size()) {
		if (vc[x][i] == vc[y][j]) {
			i++;
			j++;
		}
		else if (vc[x][i] < vc[y][j])return true;
		else return false;
	}
	if (i == vc[x].size()&&j!=vc[y].size())return true;
	else return false;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i <= n; i++) {
		cin >> s;
		a.push_back(s);
	}
	for (int i = 0; i <= n; i++) {
		string tmp;
		for (int j = 0; j < a[i].length();j++) {
			char c = a[i][j];
			if (!isdigit(c)) {
				if (tmp.length() != 0) {
					vc[i].push_back(stof(tmp));
					tmp.clear();
				}
				vc[i].push_back(c+1e10);
			}
			else {
				tmp.push_back(c);
			}
		}
		if (tmp.length() != 0) {
			vc[i].push_back(stof(tmp));
		}
	}
	for (int i = 1; i <= n; i++) {
		if (cmp(i,0))cout << '-' << endl;
		else cout << '+' << endl;
	}
	return 0;
}

 

B. Arithmetic Progressions

 

似乎应该是dp做，但是队友剪枝也卡过了。

#include <bits/stdc++.h>
typedef long long LL;
const int N=5000+7;
using namespace std;
int n, a[N], ans;
set<int> st;
 
int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;++i)
        scanf("%d", &a[i]), st.insert(a[i]);
    sort(a+1, a+1+n);
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            if(n-j+1+1<=ans) break;
            int d=a[j]-a[i];
            int x=a[j]+d;
            int cnt=2;
            while(x<=a[n]){
                if(st.count(x)) cnt++, x+=d;
                else break;
            }
            ans=max(cnt, ans);
            if(ans==n-i+1) break;
        }
    }
    printf("%d\n", ans);
    return 0;
}

 

C. Emergency Evacuation

 

把每一个人转换成他距离出口的步数，如果两个人的距离相等，说明他们中肯定有一个人要等着，则这个人的距离+1，若+1后导致与他后面的人距离又相等了，则他后面那个人距离+1，以此类推，最后一个人的最终距离就是最后答案。

刚开始以为只要有人距离相同，他后面的所有人距离都要+1，其实不是这样，因为如果后面的人离他足够远的话，是不会被堵住的。

先把距离排序，再用优先队列，如果当前人比队列顶上人距离近或距离相等则说明堵住了，或者已经在排队了，则当前人距离要变成顶上人距离+1.

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int a[500050];
int r, s, p, x, y, tmp;
long long ans = 0;
priority_queue<int, vector<int>, less<int> >q;
int main()
{
	scanf("%d %d %d", &r, &s, &p);
	for (int i = 0; i<p; i++) {
		scanf("%d %d", &x, &y);
		if (y <= s) y--;
		tmp = r - x + abs(y - s) + 1;
		a[i] = tmp;
	}
	sort(a, a + p);
	ans = 0;
	q.push(a[0]);
	for (int i = 1; i < p; i++) {
		if (a[i] <= q.top()) {
			a[i] = q.top() + 1;
		}
		q.push(a[i]);
	}
	cout << q.top() << endl;
	return 0;
}

 

D. Shortest Common Non-subsequence

 

序列自动机+dp

dp[len_p+1] [len_q+1]是最终的结果，现在需要沿着next指针走到该点，求最短路。

其实现在还是不能理解这个dp的含义，为什么要走到这里，以及这样可以保证最短，但怎么保证字典序最小？

记一下阶段性的理解：

• 为什么要走到这里？

  首先，考虑一下dp[len_p+1] [len_q+1]前面一个点，假设点(i,j)通过k=1走到了(len_p+1,len_q+1)，这说明p串后没有字符1，q串后没有字符1。

  再考虑从(0,0)出发一直走到上述的(i,j)点，这一部分路径一直走的next指针，说明这一过程产生的串一定是P[0:i]串和q[0:j]串的公共序列。

  这样我们的答案串就由两部分组成，前一部分一定是两串的公共子序列，而这个子序列在p，q中分别以 $p_i，q_j$ 结尾，最后一个字符一定是i,j后p，q串中从未出现过的字符。这样组成的答案一定不是p，q的子序列。

  注意，这里所说的i，j后从未出现过的字符，可能是在p，q串中没有，也可能是i，j已经是p，q的末尾了，p，q串之后就没有字符了。

• 为什么这样可以保证字典序最小？

  首先，这样能保证这是最短路径，这是毫无疑问的，毕竟这dp是经典的找最短路。

  其次，在第二块的双重for循环中，每次都是先找k=0，再找1，并且如果k=0符合条件，则直接break，不考虑k=1.由于我们是正向地向ans中添加字符，所以这一定是字典序最小。

输出路径的过程也很重要，以sample 3为例：q串有这么多0，为什么最终只输出了1个0？我们固定p串中指针i，再看q串，不论j在哪个位置，走1只会走到len_q+1，那么最终我们j=nxtq[t]，就直接到了len_q+1，不论0和len_q+1中间有几个0，都会跳过。

还有一点，sample 3中走10和01都可以到结尾，而选择了01，正是因为第二块循环中的break。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
char p[4005], q[4005];
int nxtp[4005][2], nxtq[4005][2], dp[4005][4005];
string ans;
void get_next(char* s, int nxt[][2], int len) {
	nxt[len + 1][0] = nxt[len + 1][1] = len + 1;
	nxt[len][0] = nxt[len][1] = len + 1;
	for (int i = len; i >= 0; i--) {
		for (int j = 0; j < 2; j++) {
			nxt[i][j] = nxt[i + 1][j];
		}
		nxt[i][s[i + 1] - '0'] = i + 1;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> p + 1 >> q + 1;
	int len_p = strlen(p + 1), len_q = strlen(q + 1);
	get_next(p, nxtp, len_p);
	get_next(q, nxtq, len_q);
	memset(dp, 0x3f, sizeof(dp));
	dp[len_p + 1][len_q + 1] = 0;
	for (int i = len_p + 1; i >= 0; i--) {
		for (int j = len_q + 1; j >= 0; j--) {
			for (int k = 0; k < 2; k++) {
				if (dp[nxtp[i][k]][nxtq[j][k]] != INF)
					dp[i][j] = min(dp[i][j], dp[nxtp[i][k]][nxtq[j][k]] + 1);
			}
		}
	}
	for (int i = 0, j = 0; i <= len_p || j <= len_q;) {
		for (int k = 0; k < 2; k++) {
			if (dp[i][j] == dp[nxtp[i][k]][nxtq[j][k]] + 1) {
				ans.push_back('0' + k);
				i = nxtp[i][k];
				j = nxtq[j][k];
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

 

G. What Goes Up Must Come Down

 

树状数组

由于是中间突起的函数，所以两边一定是最小的，考虑从小到大确定数的位置，由于先把小数都堆积在了两边，而大数都被挤到了中间，所以在考虑大数时，由于不需要经过小数，所以已经处理好的数对正在处理的数没有影响，所以可以放心地删除已经处理好的数。

树状数组记录每个位置左边比它大的数的个数，移动这个位置上的数到两边时，比他大的数的个数就是它要移动的步数（因为比它小的数都已经先于它处理好了）。

每次处理完之后把当前数所在的所有位置都删除。

注意对于一个数，要同时处理它的所有位置，且要先把该数所在的所有位置都删除之后，才能开始计算该数，否则会导致几个相同的数之间进行不必要的交换。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, N;
ll ans;
vector<int>vc[maxn];
int tr[maxn];
int lowbit(int x) {
	return x & (-x);
}
void add(int x, int b) {
	for (int i = x; i <= N; i += lowbit(i)) {
		tr[i] += b;
	}
}
int query(int r) {
	int ans = 0;
	for (int i = r; i > 0; i-=lowbit(i)) {
		ans += tr[i];
	}
	return ans;
}
int main() {
	scanf("%d", &n);
	N = n;
	for (int i = 1; i <= n; i++) {
		int u;
		scanf("%d", &u);
		vc[u].push_back(i);
		add(i, 1);
	}
	for (int i = 1; i < maxn; i++) {
		for (int j = 0; j < vc[i].size(); j++) {
			add(vc[i][j], -1);
			n--;
		}
		for (int j = 0; j < vc[i].size(); j++) {
			ans += min(query(vc[i][j] - 1), n - query(vc[i][j]));
		}
	}
	printf("%I64d\n", ans);
	return 0;
}