2019 ICPC 南昌网络赛

solve ： 3/10

补题： 5/10

https://www.jisuanke.com/contest/3870?view=challenges

B. Fire-Fighting Hero

大概就是跑两个最短路，然后由于出题人的**英语，*****

#include<bits/stdc++.h>
using namespace std;
const int MAX = 2e6+5;
const int MAXN = 1e3+5;
const int INF = 0x3f3f3f3f;
int n,m,s,k,c,first[MAXN],nextt[MAX],u[MAX],v[MAX],w[MAX],cnt=0;
int dd[MAXN],dis[MAXN],num1,num2;
int book[MAXN][MAXN];
bool vis[MAXN];
struct point{
	int dot,length;
};
bool operator<(point a,point b){
	return a.length>b.length;
}
void add(int a,int b,int c){
	u[cnt]=a,v[cnt]=b,w[cnt]=c;
	nextt[cnt]=first[u[cnt]];
	first[u[cnt]]=cnt;++cnt;
}
void dijkstra(int start,int op){
	priority_queue<point> list1;
	for(int i=1;i<=n;++i) vis[i]=false,dis[i]=INF;
	if(op==0){
		dis[start]=0;
		list1.push({start,dis[start]});
	}
	else{
		for(int i=1;i<=k;++i){
			dis[dd[i]]=0;
			list1.push({dd[i],dis[dd[i]]});
		}
	}
	while(!list1.empty()){
		point now = list1.top();
		list1.pop();
		if(vis[now.dot]) continue;
		vis[now.dot]=true;
		for(int num = first[now.dot];num!=-1;num=nextt[num]){
			if(dis[v[num]]>dis[u[num]]+w[num]){
				dis[v[num]]=dis[u[num]]+w[num];
				list1.push({v[num],dis[v[num]]});
			}
		}
	}
	if(op==0)
		for(int i=1;i<=n;++i)
			num1 = max(num1,dis[i]);
	else
		for(int i=1;i<=n;++i)
			num2 = max(num2,dis[i]);
}
void solve(){
	int t;
	scanf("%d",&t);
	while(t--){
		cnt=0,num1=0,num2=0;
		scanf("%d%d%d%d%d",&n,&m,&s,&k,&c);
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				book[i][j]=INF;
		for(int i=1;i<=n;++i) first[i]=-1;
		for(int i=1;i<=k;++i) scanf("%d",&dd[i]);
		for(int i=1;i<=m;++i){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			book[a][b]=min(book[a][b],c);
			book[b][a]=min(book[b][a],c);
		}
		for(int i=1;i<=n;++i){
			for(int j=i+1;j<=n;++j){
				if(book[i][j]!=INF){
					add(i,j,book[i][j]);
					add(j,i,book[i][j]);
				}
			}
		}
		dijkstra(s,0);
		dijkstra(dd[1],1);
		if(num1<=num2*c) printf("%d\n",num1);
		else printf("%d\n",num2);
	}
}
int main(void)
{
	solve();
	return 0;
}

C. Hello 2019

人均打爆 tourist 的题。

让一个串的一段（子串）只包含2019不包含2018删除最少的字符数量。

考虑使用矩阵来维护每一个位置/子串的状态，

0 ->

1 -> 2

2 -> 20

3 -> 201

4 -> 2019

4 -> 2018

合并两个状态的时候，考虑将两个矩阵合成一个矩阵，考虑类似于floyd的三层循环来解决。

这样我们就可以在 n 的时间内求出一个询问，总时间复杂度是 n*q ，显然会超时。

于是考虑用线段树维护，只需要 logn 的时间就可以求出这一段区间的贡献，总复杂度 qlogn

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)>>1;
using namespace std;
const int MAXN = 2e5 + 5;
const ll inf = 2e5 + 10;
struct Martix
{
	int jzk[5][5];
	void zero()
	{
		memset(jzk, 0, sizeof(jzk));
	}
	void one()
	{
		zero();
		for (int i = 0; i < 5; i++)
			jzk[i][i] = 1;
	}
	void MAX()
	{
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				jzk[i][j] = inf;
	}
};
Martix operator * (Martix a, Martix b)
{
	Martix ans;
	ans.MAX();
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			for (int k = 0; k < 5; k++)
				ans.jzk[i][j] = min(ans.jzk[i][j], a.jzk[i][k] + b.jzk[k][j]);
	return ans;
}
struct node
{
	int l;
	int r;
	Martix a;
}que[MAXN * 4];
int n, q, ql, qr;
char s[200005], s1[200005];
void up(int k)
{
	que[k].a = que[k << 1].a * que[k << 1 | 1].a;
}
void build(int left = 1, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	if (left == right)
	{
		que[k].a.MAX();
		for (int i = 0; i < 5; i++)
			que[k].a.jzk[i][i] = 0;
		if (s[left] == '2')
			que[k].a.jzk[0][0] = 1, que[k].a.jzk[0][1] = 0;
		else if (s[left] == '0')
			que[k].a.jzk[1][1] = 1, que[k].a.jzk[1][2] = 0;
		else if (s[left] == '1')
			que[k].a.jzk[2][2] = 1, que[k].a.jzk[2][3] = 0;
		else if (s[left] == '9')
			que[k].a.jzk[3][3] = 1, que[k].a.jzk[3][4] = 0;
		else if (s[left] == '8')
			que[k].a.jzk[3][3] = 1, que[k].a.jzk[4][4] = 1;
		return;
	}
	imid;
	build(lson);
	build(rson);
	up(k);
}
Martix query(int left = 1, int right = n, int k = 1)
{
	if (ql <= left && right <= qr)
		return que[k].a;
	imid;
	if (qr <= mid)
		return query(lson);
	else if (ql > mid)
		return query(rson);
	else
		return query(lson) * query(rson);
}
int main()
{
	sc("%d%d", &n, &q);
	sc("%s", s1 + 1);
	for (int i = n; i >= 1; i--)
		s[i] = s1[n - i + 1];
	build();
	while (q--)
	{
		sc("%d%d", &ql, &qr);
		ql = n - ql + 1;
		qr = n - qr + 1;
		swap(ql, qr);
		Martix ans = query();
		ll res = ans.jzk[0][4];
		if (res >= inf)
			pr("-1\n");
		else
			pr("%lld\n", res);
	}
}

E. Magic Master

出题人麻烦出现解释一下为什么 Tnm=4e9，能在6s跑完

暴力跑约瑟夫环

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)>>1;
using namespace std;
int ans[40000005];
int in[105];
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n, m, q, maxn = 0;
		sc("%d%d%d", &n, &m, &q);
		for (int i = 0; i < q; i++)
		{
			sc("%d", &in[i]);
			maxn = max(maxn, in[i]);
		}
		deque<int>deq;
		for (int i = 1; i <= n; i++)
			deq.push_back(i);
		for (int i = 1; i <= n; i++)
		{
			ans[deq.front()] = i;
			deq.pop_front();
			if (i > maxn)
				break;
            int tt=m%deq.size();
			for (int j = 0; j < tt; j++)
			{
				int t = deq.front();
				deq.pop_front();
				deq.push_back(t);
			}
		}
		for (int i = 0; i < q; i++)
			pr("%d\n", ans[in[i]]);
	}
}

H. The Nth Item

群老哥说这种一个数*一个数字的平方，这种生成器，是有循环节的，而且还比较小，所以矩阵乘法跑1e7次+记忆化搜索是不会T的，实测。

其实正解应该是分块吧。

将一个大整数分为3个六块，预处理每一块的答案，然后乘一下就是最终答案。

记忆化:

正确通过

2019-09-08 21:26

315ms

1624kB

c++

#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
const ll mod = 998244353;
map<ll, ll>mp;
struct node
{
	ll a[2][2];
	void zero()
	{
		memset(a, 0, sizeof(a));
	}
	void one()
	{
		zero();
		a[0][0] = a[1][1] = 1;
	}
	void pre()
	{
		a[0][0] = 1;
		a[1][0] = 0;
		a[0][1] = 0;
		a[1][1] = 0;
	}
	void temp()
	{
		a[0][0] = 3;
		a[0][1] = 2;
		a[1][0] = 1;
		a[1][1] = 0;
	}
	node operator * (node other)
	{
		node ans;
		ans.zero();
		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < 2; j++)
			{
				for (int k = 0; k < 2; k++)
				{
					ans.a[i][j] += a[i][k] * other.a[k][j];
					ans.a[i][j] %= mod;
				}
			}
		}
		return ans;
	}
};
ll qqq[4];
node power(node a, ll b)
{
	node res;
	res.one();
	while (b)
	{
		if (b & 1)
			res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
node qwe[61];
ll get(ll n)
{
	n++;
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	node t;
	t.temp();
	node a;
	a.pre();
	node ans;
	ans.one();
	ll num = n - 2;
	for (int i = 0; i <= 60; i++)
	{
		if ((1LL << i) & num)
			ans = ans * qwe[i];
	}
	ans = ans * a;
	return ans.a[0][0];
}
int main()
{
	node t;
	t.temp();
	qwe[0].temp();
	for (int i = 1; i <= 60; i++)
	{
		qwe[i] = power(t, 1LL << i);
	}
	ll q, n;
	sc("%lld%lld", &q, &n);
	ll ans = 0;
	while (q--)
	{/*
		sc("%lld", &n);
		ll re = get(n);
		pr("%lld\n", re);*/
		ll res = 0;
		if (mp.count(n) == 0)
		{
			res = get(n);
			mp[n] = res;
		}
		else
			res = mp[n];
		ans ^= res;
		n = (n ^ (res * res));
		//pr("%lld\n", n);
	}
	pr("%lld\n", ans);
}
//90353790

分块：

正确通过

2019-09-10 19:14

799ms

125352kB

c++

#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
const ll mod = 998244353;
map<ll, ll>mp;
struct node
{
	ll a[2][2];
	void zero()
	{
		memset(a, 0, sizeof(a));
	}
	void one()
	{
		zero();
		a[0][0] = a[1][1] = 1;
	}
	void pre()
	{
		a[0][0] = 1;
		a[1][0] = 0;
		a[0][1] = 0;
		a[1][1] = 0;
	}
	void temp()
	{
		a[0][0] = 3;
		a[0][1] = 2;
		a[1][0] = 1;
		a[1][1] = 0;
	}
	node operator * (node other)
	{
		node ans;
		ans.zero();
		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < 2; j++)
			{
				for (int k = 0; k < 2; k++)
				{
					ans.a[i][j] += a[i][k] * other.a[k][j];
					ans.a[i][j] %= mod;
				}
			}
		}
		return ans;
	}
};
ll qqq[4];
node power(node a, ll b)
{
	node res;
	res.one();
	while (b)
	{
		if (b & 1)
			res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
node qwe[4][1000005];
ll get(ll n)
{
	n++;
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	node t;
	t.temp();
	node a;
	a.pre();
	node ans;
	ans.one();
	ll num = n - 2;
	ans = qwe[0][num % 1000000] * qwe[1][(num / 1000000) % 1000000] * qwe[2][(n / 1000000000000) % 1000000] * qwe[3][(n / 1000000000000000000) % 1000000];
	ans = ans * a;
	return ans.a[0][0];
}
void init()
{
	node t;
	t.temp();
	qwe[0][0].one();
	qwe[1][0].one();
	qwe[2][0].one();
	qwe[3][0].one();
	for (int i = 1; i <= 1000000; i++)
		qwe[0][i] = qwe[0][i - 1] * t;
	for (int i = 1; i <= 1000000; i++)
		qwe[1][i] = qwe[1][i - 1] * qwe[0][1000000];
	for (int i = 1; i <= 1000000; i++)
		qwe[2][i] = qwe[2][i - 1] * qwe[1][1000000];
	for (int i = 1; i <= 10; i++)
		qwe[3][i] = qwe[3][i - 1] * qwe[2][1000000];
}
int main()
{
	init();
	ll q, n;
	sc("%lld%lld", &q, &n);
	ll ans = 0;
	while (q--)
	{
		ll res = 0;
		res = get(n);
		ans ^= res;
		n = (n ^ (res * res));
		//pr("%lld\n", n);
	}
	pr("%lld\n", ans);
}
//90353790