[数据结构与算法][补题]ICPC Mid-Central USA Region 2019

8.19的牛客模拟赛
暑假里做了很多这种区域赛，但是还没有补题，最近会慢慢补完
传送门

A. Commemorative Race

题意

在一个有向无环图中，将其最长路的一条边删掉，然后再从这个起点开始，求所能达到的最长路径中的最小值。

题解

通过两次$dfs$解决，首先建立一个“超级源点”，向所有的点连边

• 第一次$dfs$，从“超级源点”开始，处理出以$i$点为起点能够达到的最长路径和次长路径长度——$maxlen[i]$和$maxlen1[i]$
• 第二次$dfs$，从“超级源点”开始，沿着最长路径走，并更新答案数组为 当前长度+以当前点为起点的次长路径长度

最后在ans数组中取最小值（注意只统计长度出现过一次的路径，原因还没想明白，留个坑）

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
const int MAXM = 2e6+99;
int num_edge,n,m,x,y,maxlen[MAXN],maxlen2[MAXN], head[MAXN];
struct Edge{
	int next, to;
}edge[MAXM];
bool vis[MAXN], b[MAXN];
int cnt[MAXN], ans[MAXN];

void add_edge(int from, int to)
{
	edge[++num_edge].next = head[from];
	edge[num_edge].to = to;
	head[from] = num_edge;
}

int dfs(int x)
{
	if (vis[x]) return maxlen[x];
	vis[x] = 1;
	int tmp = 0;
	for (int i = head[x]; i; i = edge[i].next)
	{
		int to = edge[i].to;
		tmp = dfs(to) + 1;
		if (tmp > maxlen[x])
		{
			maxlen2[x] = maxlen[x];
			maxlen[x] = tmp;
		}
		else if (tmp > maxlen2[x])
			maxlen2[x] = tmp;
	}
	return maxlen[x];
}

void dfs2(int x, int len)
{
	if (b[x]) return;
	b[x] = 1;
	for (int i = head[x]; i; i = edge[i].next)
	{
		int to = edge[i].to;
		if (maxlen[x] == maxlen[to] + 1)
		{
			dfs2(to, len + 1);
			cnt[len] ++;
			ans[len] = len + maxlen2[x];
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i ++) add_edge(0,i);
	for (int i = 1; i <= m; i ++)
	{
		scanf("%d%d",&x,&y);
		add_edge(x,y);
	}
	dfs(0);
	dfs2(0,0);
	int minn = maxlen[0];
	for (int i = 1; i <= n; i ++)
		if (cnt[i] == 1)
			minn = min(minn, ans[i]);
	printf("%d",minn - 1);
	return 0;
}

B. Convoy

题意

有n个人和k辆车，每辆车上最多坐5个人，每个人都可以驾驶该车辆，并且其驾驶时间不同，问最少多长时间可以把这n个人从网目的地（司机可以回来拉人）

题解

尝试用贪心，当然是让驾驶速度最快的司机一直跑，其总时间等于最慢的那个司机的时间，但是这个过程并不好模拟。
于是就想到了二分，二分一个时间，看看能不能在规定时间内把人们都送到目的地。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
int n, k;
ll a[50000];

bool judge(ll t)
{
	ll ans = 0;
	for (int i = 1; i <= k; i ++)
	{
		if (a[i] > t) return 0; 
		ll tt = t/a[i];
		ll cnt = (tt-1)/2 + 1;
		ans += 4*cnt + 1;
		if (ans >= n) return 1;//这个放在里面 否则可能会超long long 
	}
	return 0;
}

int main()
{
	scanf("%d%d",&n,&k);
	ll l = 0; ll r = 0;
	for (int i = 1; i <= n; i ++)
		scanf("%lld",&a[i]), r += a[i];
	sort(a + 1, a + 1 + n);
	while (l < r)
	{
		ll mid = (l + r) / 2;
		if (judge(mid))
			r = mid;
		else l = mid + 1;
	}
	printf("%lld",l);
	return 0;
} 

E. Dragon Ball I

题意

在图中有7个点被标记（点可能重复），从一号点开始，按任意顺序访问这7个点的最短路径长度。

题解

分别以这七个点为起点，跑迪杰斯特拉，然后使用next_permutation 枚举7的全排列。
在实现过程上有很多细节，比如开long long，点的编号和下标等等，WA了很多次。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 1010000;
#define ll long long
#define inf 1000000000000000000
ll n, m, s[10];
ll dis[10][MAXN], d[10][10], head[MAXN], num;
bool vis[MAXN];

struct Edge{
	ll next, to, dis;
}e[MAXN];

struct Node {
	ll dis, id;
	bool operator <(const Node& x) const {
		return dis > x.dis;}
};

void add_edge(ll from, ll to, ll dis)
{
	e[++num].next = head[from];
	e[num].to = to;
	e[num].dis = dis;
	head[from] = num;
}

void dij(ll ss, ll id)
{
	priority_queue <Node> q;
	for (ll i = 0; i <= n; i ++)
		dis[id][i] = inf;
	dis[id][ss] = 0;
	q.push( (Node){0,ss} );
	memset(vis,0,sizeof(vis));
	while (!q.empty())
	{
		Node now = q.top();
		q.pop();
		if (vis[now.id]) continue;
		vis[now.id] = 1;
		for (ll i = head[now.id]; i; i = e[i].next)
		{
			ll to = e[i].to;
			if (dis[id][to] > dis[id][now.id] + e[i].dis)
			{
				dis[id][to] = dis[id][now.id] + e[i].dis;
				if (!vis[to])
					q.push((Node){dis[id][to],to});
			}
		}
	}
}

int main()
{
	scanf("%lld %lld",&n,&m);
	for (int i = 1; i <= m; i ++)
	{
		ll x, y, z;
		scanf("%lld %lld %lld",&x,&y,&z);
		add_edge(x,y,z); add_edge(y,x,z);
	}
	for (int i = 1; i <= 7; i ++)
		scanf("%lld",&s[i]);
	for (int i = 1; i <= 7; i ++)
		dij(s[i],i);
	for (int i = 1; i <= 7; i ++)
		for (int j = i; j <= 7; j ++)
			d[i][j]=d[j][i]=dis[i][s[j]];
	ll a[] = {0,1,2,3,4,5,6,7};
	ll ans = inf;
	do
	{
		ll tmp = d[a[1]][1];
		for (int i = 2; i <= 7; i ++)
			tmp += d[a[i-1]][a[i]];
		ans = min(ans, tmp);
	}while(next_permutation(a + 1, a + 8));
	if (ans >= inf) ans = -1;
	printf("%lld\n",ans);
	
	return 0;
} 

G. Farming Mars

题意

求在$[l,r]$区间中出现次数大于等于区间长度一半（包含端点）的数

题解

关键是在于理解$[(r?l+1)/2]+1$的含义是区间长度的一半
还要掌握$O(n)$的算法，即，当前数与上一个数相同，则cnt++，并记录这个位置，否则，cnt–。这样，一定可以找到出现次数大于等于二的数

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
using namespace std;
const int MAXN = 10001;
#define ll long long
int n, m, l, r, a[MAXN];

void work()
{
	int d = (r-l+1)/2 + 1;
	int num = a[l], cnt = 1;
	for (int i = l+1; i <= r; i ++)
	{
		if (a[i] == num) cnt ++;
		else cnt --;
		if (cnt == 0)
		{
			num = a[i];
			cnt = 1;
		}
	}
	cnt = 0;
	for (int i = l; i <= r; i ++)
		if (a[i] == num) cnt ++;
	if (cnt >= d) printf("usable\n");
	else printf("unusable\n");
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i ++)
	{
		double x; scanf("%lf",&x);
		x *= 1000000;
		a[i] = x;
	}
	for (int i = 1; i <= m; i ++)
	{
		scanf("%d%d",&l,&r);
		work();
	}
	return 0;
} 

H. Soft Passwords

按题意细心模拟即可，细节较多

#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
string s, p;

int main()
{
	cin >> s; cin >> p;
	int lens = s.length();
	int lenp = p.length();
	if (s == p) {
		printf("Yes"); return 0;
	}
	if (lens == lenp)
	{
		string tmp = s;
		for (int i = 0; i < lenp; i ++)
			if ('a' <= s[i]&&s[i] <= 'z' )
			{
				tmp[i] = s[i] - ('a' - 'A');
			}
			else if ('A' <= s[i]&&s[i] <= 'Z')
				tmp[i] = s[i] + ('a' - 'A');
		if (tmp == p) printf("Yes");
		else printf("No");
		return 0;
	}
	if (!(lens-lenp == 1)) {
		printf("No");
		return 0;
	}
	if ('0' <=s[0]&&s[0] <= '9')
	{
		if (s == (s[0]+p)) printf("Yes");
		else printf("No");
		return 0;
	}
	if ('0' <=s[lens-1]&&s[lens-1] <= '9')
	{
		if (s == (p+s[lens-1])) printf("Yes");
		else printf("No");
		return 0;
	}
	printf("No");
	return 0;
} 

I. Sum and Product

题意

给一串数，区间内的连乘积等于连加和，问有多少个这样的区间。

题解

我们知道，多个数连乘比多个数连加具有更大的贡献， 但是1这个数字很特殊，它会使和增加而不会使乘积增加。
如果a[i] == 1 ,我们使用end1[i]来记录这一串1从哪里结束
然后我们枚举起点，如果遇到1，那么就判断当前的和加上所有的1之后能不能比乘积大（当然，和必须是小于积的）
同时，我们记录一个后缀和，如果当前的和加上后缀和依然小于乘积，及时退出，优化。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
const int MAXN = 2e6+11;
int n, end1[MAXN];
ll a[MAXN], rsum[MAXN];

int main()
{
	scanf("%d",&n);
	for (int i = 1; i <= n; i ++)
		scanf("%lld",&a[i]);
	for (int i = n; i >= 1; i --)
	{
		rsum[i] = rsum[i+1] + a[i];
		if (a[i] == 1)
			end1[i] = max(end1[i+1], i);
	}
	ll ans = 0;
	for (int i = 1; i <= n; i ++)
	{
		ll mul = a[i];
		ll sum = a[i];
		for (int j = i+1; j <= n; j ++)
		{
			if (a[j] == 1)
			{
				int cnt1 = end1[j] - j + 1;
				if (sum < mul && sum + cnt1 >= mul)
					ans ++;
				sum += cnt1;
				j = end1[j];
				continue;
			}
			mul *= a[j];
			sum += a[j];
			if (mul == sum) ans ++;
			if (sum + rsum[j+1] < mul) break;
		}
	}
	printf("%lld",ans);
	return 0;
}
/*
5
2 2 1 2 3
*/

J. True/False Worksheet

题意

给一串数，并给出$[l,r]$区间内的数是否都相同或者不都相同的信息
问满足条件的序列有多少个

题解

这是一道DP
首先O(n)处理出$sm$数据和$df$数组，$sm[i]$表示i位置左边最远的相同的数的位置，$df[i]$表示i位置左边最近的不同的数的位置。
用$f[i][j]$表示前i位中有j位已经确定时的方法数,状态转移方程如下：

	f[0][0] = 1;
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j < i; j ++)
		{
			if (j < sm[i] && df[i] <= j)
				f[i][j] = (f[i][j] + f[i-1][j]) % MOD;
			if (sm[i] == i && df[i] < i)
				f[i][i-1] = (f[i][i-1] + f[i-1][j]) % MOD;
		}

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int MOD = 1e9+7;
int n,m, f[5001][5001],sm[5001],df[5001];

int main()
{
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i ++)
	{
		sm[i] = i; df[i] = -1;
	}
	int x ,y; char s[101];
	for (int i = 1; i <= m; i ++)
	{
		scanf("%d%d%s",&x,&y,s);
		if (s[0] == 's')
			sm[y] = min(sm[y], x);
		else df[y] = max(df[y], x);
	}
	f[0][0] = 1;
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j < i; j ++)
		{
			if (j < sm[i] && df[i] <= j)
				f[i][j] = (f[i][j] + f[i-1][j]) % MOD;
			if (sm[i] == i && df[i] < i)
				f[i][i-1] = (f[i][i-1] + f[i-1][j]) % MOD;
		}
	int ans = 0;
	for (int i = 0; i < n; i ++)
		ans = (ans + f[n][i]) % MOD;
	printf("%d",ans);
	return 0;
}

K. Umm Code

模拟，注意um单词后面可能带有标点符号

#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
const int MAXN = 500005;
using namespace std;
char a[MAXN];
int tot;
char s[MAXN];

void work(string str)
{
	int cnt = 1;
	int ans = 0;
	for (int i = 6; i >= 0; i --)
	{
		if (str[i] == '1')
			ans += cnt;
		cnt *= 2;
	}
	printf("%c",ans);
}

int main()
{
	while (scanf("%s",s) != EOF)
	{
		int n = strlen(s);
		bool flag = 0;
		for (int i = 0; i < n; i ++)
			if (s[i] != 'u' && s[i] != 'm')
			{
				if (!('0'<=s[i]&&s[i]<='9' || 'a'<=s[i]&&s[i]<='z' || 'A'<=s[i]&&s[i]<='Z' || s[i] ==' '))
					continue;
				flag = 1; break;
			}
		if (flag) continue;
		for (int i = 0; i < n; i ++)
			if (s[i] == 'u') a[++tot] = '1';
			else if (s[i] == 'm') a[++tot] = '0';
	}
	for (int i = 1; i <= tot; i += 7)
	{
		if (i+6 > tot) break;
		string tmp = "";
		for (int j = 0; j <= 6; j ++)
			tmp += a[i+j];
		work(tmp);
	}
	return 0;
} 
/*
uu Friends m Romans ummuuummmuuuuumm countrymen mmuummmuu
*/