『ACM-XCPC』2020暑期ZJNU个人排位1

USACO19DEC

Posted by GJ on April 11, 2020

A Cow Gymnastics B

Description

为了提高健康水平,奶牛们开始进行体操训练了!Farmer John 选定了他最喜爱的奶牛 Bessie 来执教其他 N 头奶牛,同时评估她们学习不同的体操技术的进度。

K (1 ≤ K ≤ 10)次训练课的每一次,Bessie 都会根据 N (1 ≤ N ≤ 20) 头奶牛的表现给她们进行排名。之后,她对这些排名的一致性产生了好奇。称一对不同的奶牛是一致的,如果其中一头奶牛在每次训练课中都表现得都比另一头要好。

请帮助 Bessie 计算一致的奶牛的对数。

Input

输入的第一行包含两个正整数 KN。以下 K 行每行包含整数 1 … N的某种排列,表示奶牛们的排名(奶牛们用编号 1 … N 进行区分)。如果在某一行中 A 出现在 B 之前,表示奶牛 A 表现得比奶牛 B 要好。

Output

输出一行,包含一致的奶牛的对数。

Sample Input

3 4
4 1 2 3
4 1 3 2
4 2 1 3

Sample Output

4

Solution

暴力

Code

#include<set>
#include<map>
#include<stack>
#include<utility>
#include<ctime>
#include<string>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3ff
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e2 + 10;
int mp[maxn][maxn],p[maxn];
int n,k,ans;

void solve(){
    cin>>k>>n;
	for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++) cin>>p[j];
        for(int j=1;j<=n;j++)
            for(int k=j+1;k<=n;k++)
                mp[p[j]][p[k]]++;
	}
	for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(mp[i][j]==k) ans++;
    cout<<ans<<"\n";
}

int main() {
	solve();
	return 0;
}

B Where Am I? B

Description

Farmer John 出门沿着马路散步,但是他现在发现可能迷路了!

沿路有一排共 N (1 ≤ N ≤ 100) 个农场。不幸的是农场并没有编号,这使得 Farmer John 难以分辨他在这条路上所处的位置。然而,每个农场都沿路设有一个彩色的邮箱,所以 Farmer John 希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。

每个邮箱的颜色用 A..Z 之间的一个字母来指定,所以沿着道路的 N 个邮箱的序列可以用一个长为 N 的由字母 A..Z 组成的字符串来表示。某些邮箱可能会有相同的颜色。Farmer John 想要知道最小的 KK 的值,使得他查看任意连续 K 个邮箱序列,他都可以唯一确定这一序列在道路上的位置。

例如,假设沿路的邮箱序列为 ABCDABC 。Farmer John 不能令K=3,因为如果他看到了 ABC,沿路有两个这一连续颜色序列可能所在的位置。最小可行的 K 的值为 K=4,因为如果他查看任意连续 4 个邮箱,这一颜色序列可以唯一确定他在道路上的位置。

Input

输入的第一行包含 N,第二行包含一个由 N 个字符组成的字符串,每个字符均在 A..Z 之内。

Output

输出一行,包含一个整数,为可以解决 Farmer John 的问题的最小 K 值。

Sample Input

7
ABCDABC

Sample Output

4

Solution

暴力大法好

Code

#include<set>
#include<map>
#include<stack>
#include<utility>
#include<ctime>
#include<string>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3ff
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e2 + 10;
int n,ans=0,mp[maxn];
string s;

void solve(){
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++){
        string ss;
        for(int j=1;j+i<=n;j++){
            ss+=s[i+j-1];
            ans=0;
            for(int k=i+1;k<n;k++){
                string t;
                for(int o=1;o<=j&&j+k<=n;o++) t+=s[k+o-1];
                if(t==ss) ans++;
            }
            if(ans) mp[j]=1;
        }
    }
    for(int i=1;i<=n;i++) if(!mp[i]) {cout<<i<<"\n";break;}
}

int main() {
	solve();
	return 0;
}

C Livestock Lineup B

Description

每天,Farmer John 都要给他的 8 头奶牛挤奶。她们的名字分别是 Bessie,Buttercup,Belinda,Beatrice,Bella,Blue,Betsy和 Sue。

不幸的是,这些奶牛相当难以伺候,她们要求 Farmer John 以一种符合 N 条限制的顺序给她们挤奶。每条限制的形式为“X 必须紧邻着 Y 挤奶”,要求奶牛 X 在挤奶顺序中必须紧接在奶牛 Y 之后,或者紧接在奶牛 Y 之前。

请帮助 Farmer John 求出一种满足所有限制的奶牛挤奶顺序。保证这样的顺序是存在的。如果有多种顺序都满足要求,请输出字典序最小的一种。也就是说,第一头奶牛需要是所有可能排在任意合法奶牛顺序的第一位的奶牛中名字字典序最小的。在所有合法的以这头字典序最小的奶牛为首的奶牛顺序中,第二头奶牛需要是字典序最小的,以此类推。

Input

输入的第一行包含 N (1 ≤ N ≤ 7)。以下 N 行每行包含一句句子,以 “X must be milked beside Y” 的格式描述了一条限制,其中 XY 为 Farmer John 的某些奶牛的名字(上文列举了八个可能的名字)。

Output

请用 8 行输出一个奶牛的顺序,每行输出一头奶牛的名字,满足所有的限制。如果由多种顺序符合要求,输出字典序最小的奶牛顺序。

Sample Input

3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice

Sample Output

Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

Solution

总共就八只,因此全排列,然后判断就好啦

next_permutation 好nb!

Code

//琐碎头太长了
//之后再另外post一篇琐碎好了
#include<bits/stdc++.h>
#define INF 0x3f3f3ff
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
int n;
string s[10],a[10],b[10],none;
map<string, int>mp;

void func() {
	for (int i = 0; i <= 7; i++) mp[s[i]] = i;
	return;
}

void init() {
	s[0] = "Beatrice";
	s[1] = "Belinda";
	s[2] = "Bella";
	s[3] = "Bessie";
	s[4] = "Betsy";
	s[5] = "Blue";
	s[6] = "Buttercup";
	s[7] = "Sue";
}

int main() {
	O_O;
	init();
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i] >> none >> none >> none >> none >> b[i];
	do {
		int flag = 1;
		func();
		for (int i = 1; i <= n; i++) if (abs(mp[a[i]] - mp[b[i]]) != 1) { flag = 0; break; }
		if (flag) {
			for (int i = 0; i <= 7; i++) cout << s[i] << "\n";
			break;
		}
	} while (next_permutation(s, s + 8));
	return 0;
}

D MooBuzz S

Description

Farmer John 的奶牛们最近成为了一个简单的数字游戏“FizzBuzz”的狂热玩家。这个游戏的规则很简单:奶牛们站成一圈,依次从一开始报数,每头奶牛在轮到她的时候报一个数。如果一头奶牛将要报的数字是 3 的倍数,她应当报 Fizz 来代替这个数。如果一头奶牛将要报的数字是 5 的倍数,她应当报 Buzz 来代替这个数。如果一头奶牛将要报的数字是 15 的倍数,她应当报 FizzBuzz 来代替这个数。于是这个游戏的开始部分的记录为:

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16

由于词汇的匮乏,奶牛们玩的 FizzBuzz 中用Moo 代替了 FizzBuzzFizzBuzz。于是奶牛版的游戏的开始部分的记录为:

1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16

给定 N,请求出这个游戏中第 N 个被报的数。

Input

输入包含一个整数 N (1 ≤ N ≤ 109)

Output

输出游戏中被报出的第 N 个数。

Sample Input

4

Sample Output

7

Solution

N范围hin大,查找这样的话,就用二分啦。

大小为W的数字所在的位置为:W-W/3-W/5+W/15

二分真的是华丽花哨好看多样呢! //后续补一篇二分趴

Code

#include<bits/stdc++.h>
#define INF 0x3f3f3ff
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
ll n,ans=0;

bool check(ll v) {
	return (v - v / 3 - v / 5 + v / 15) >= n;
}

int main() {
	O_O;
	cin >> n;
	ll l = 1, r = 1e18;
	while (l <= r) {
		ll mid = l + r >> 1;
		if (check(mid)) r = mid - 1;
		else l = mid + 1;
	}
	cout << l << "\n";
	return 0;
}

E Meetings S

Description

有两个牛棚位于一维数轴上的点 0L 处。同时有 N 头奶牛位于数轴上不同的位置(将牛棚和奶牛看作点)。每头奶牛 i 初始时位于某个位置 xi,并朝着正向或负向以一个单位每秒的速度移动,用一个等于 1-1 的整数 di 表示。每头奶牛还拥有一个在范围 [1,103]内的重量。所有奶牛始终以恒定的速度移动,直到以下事件之一发生:

  • 如果奶牛 i 移动到了一个牛棚,则奶牛 i 停止移动。
  • 当奶牛 ij 占据了相同的点的时候,并且这一点不是一个牛棚,则发生了相遇。此时,奶牛 i 被赋予奶牛 j 先前的速度,反之亦然。注意奶牛可能在一个非整数点相遇。

T 等于停止移动的奶牛(由于到达两个牛棚之一)的重量之和至少等于所有奶牛的重量之和的一半的最早时刻。请求出在时刻 0 … T(包括时刻 T)之间发生的奶牛对相遇的总数。

Input

输入的第一行包含两个空格分隔的整数 N (1 ≤ N ≤ 5 · 104)L (1 ≤ L ≤ 109)

以下 N 行,每行包含三个空格分隔的整数 wixi 以及 di。所有的位置 xi 各不相同,并且满足 0 < xi < L

Output

输出一行,包含答案。

Sample Output

3 5
1 1 1
2 2 -1
3 3 -1

Sample Input

2

Solution

  1. 两头牛相遇就会改变行进方向。那么可以看成两牛相遇,方向不变,体重交换。

  2. 一旦体重序列发生改变,那么一定是相向,那么就看作一旦体重序列发生变化,就将两数交换,不让序列发生变化。
  3. 因为时间存在单调性,那么先二分时间。(要先把奶牛们按照位置从小到大排序吼!
  4. 相遇的奶牛对数的总数,按①②来看,就是两次排序同一奶牛的位置差。(第二次排序就是知道时间了之后的排序撒!

Code

#include<bits/stdc++.h>
#define INF 0x3f3f3ff
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 6e5 + 10;
ll n, m, ans = 0, sum = 0;
struct node {
	ll w;
	double x;
	ll d;
	int id;
}ed[maxn];
int ind[maxn];

bool check(ll v) {
	ll res = 0;
	ll le = 1, ri = n;
	for (int i = 1; i <= n; i++) {
		ll u = ed[i].d * v + ed[i].x;
		if (ed[i].d==1) {
			if (u >= m) res += ed[ri--].w;
		}
		else {
			if (u <= 0) res += ed[le++].w;
		}
	}
	return res * 2 >= ans;
}

bool cmp(node a, node b) {
	if (a.x == b.x) return a.id < b.id;
	return a.x < b.x;
}

int main() {
	O_O;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> ed[i].w >> ed[i].x >> ed[i].d, ed[i].id = i, ans += ed[i].w;
	sort(ed + 1, ed + 1 + n, cmp);
	for (int i = 1; i <= n; i++) ind[ed[i].id] = i;
	ll l = 0, r = m;
	while (l <= r) {
		ll mid = l + r >> 1;
		if (check(mid)) r = mid - 1;
		else l = mid + 1;
	}
	for (int i = 1; i <= n; i++) ed[i].x += ed[i].d * (l + 0.1);
	sort(ed + 1, ed + 1 + n, cmp);
	for (int i = 1; i <= n; i++) sum += abs(i - ind[ed[i].id]);
	cout << sum / 2 << "\n";
	return 0;
}

F Milk Pumping G

#include<bits/stdc++.h>
#define INF 0x3f3f3ff
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 10;
int n, m,cnt;
struct node {
	int a, b, c, f;
}ed[maxn];
int hd[maxn<<1];

struct Node { int to, nxt, val; }edge[maxn << 1];
void add(int p, int q, int o) { edge[cnt] = { q,hd[p],o }; hd[p] = cnt++; }
void init() { cnt = 0; memset(hd, -1, sizeof(hd)); }

void init() {
	cnt = 0;
	memset(hd, -1, sizeof(hd));
}

bool cmp(node x, node y) {
	return x.f < y.f;
}

int main() {
	O_O;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> ed[i].a >> ed[i].b >> ed[i].c >> ed[i].f;
	sort(ed + 1, ed + 1 + m, cmp);
	for (int i = 1; i <= m; i++) {
		add(ed[i].a, ed[i].b, ed[i].c);
		add(ed[i].b, ed[i].a, ed[i].c);

	}
	return 0;
}