2017 多校联合训练 10 题解

Problem 1001

考虑到直接搜肯定TLE。

我们从起点开始搜10步，再从终点开始搜10步。

其中，从终点开始搜10步通过预处理完成，因为每一次的终点都是一样的。

存状态的时候我把0变成6（为了调试方便），把所有数字写在一行。

然后把这个大数看成一个7进制数，刚好在long long的范围内。

状态用map存储即可。

（幸好比赛的时候做出了这题……）

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

const int N = (1 << 23) + 60;
const int Q = 63;

const LL w[Q] = {0, 6, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5};

LL  bit[Q], pre;
int p[Q][Q], a[Q], T, pos, ans, cnt = 0;

vector <int> v[Q];
map    <LL, int> MP, mp;

void dfs(int x, int z, LL now){

	if (!mp[now]) mp[now] = x;
	else mp[now] = min(mp[now], x);

	if (x > 10) return;

	for (auto u : v[z]){
		LL ooo = 21 - z;
		LL ol  = now / bit[ooo];
		LL lo  = ol % 7;

		LL eee = 21 - u;
		LL el  = now / bit[eee];
		LL le  = el % 7;

		LL fff = now - lo * bit[ooo] - le * bit[eee] + lo * bit[eee] + le * bit[ooo];
		dfs(x + 1, u, fff);
	}
}

void pre_dfs(int x, int z, LL now){

	if (!MP[now]) MP[now] = x;
	else MP[now] = min(MP[now], x);

	if (x > 10) return;

	for (auto u : v[z]){
		LL ooo = 21 - z;
		LL ol  = now / bit[ooo];
		LL lo  = ol % 7;


		LL eee = 21 - u;
		LL el  = now / bit[eee];
		LL le  = el % 7;

		LL fff = now - lo * bit[ooo] - le * bit[eee] + lo * bit[eee] + le * bit[ooo];

		pre_dfs(x + 1, u, fff);

	}
}

int main(){

	bit[0] = 1;
	rep(i, 1, 21) bit[i] = bit[i - 1] * 7LL;

	rep(i, 1, 6){
		rep(j, 1, i){
			++cnt;
			p[i][j] = cnt;
		}
	}

	rep(i, 1, 6){
		rep(j, 1, i){
			int nx = i - 1, ny = j - 1;
			if (nx > 0 && ny > 0 && p[nx][ny]){
				v[p[i][j]].push_back(p[nx][ny]);
			}

			nx = i - 1, ny = j;
			if (nx > 0 && ny > 0 && p[nx][ny]){
				v[p[i][j]].push_back(p[nx][ny]);
			}
			nx = i + 1, ny = j;
			if (nx > 0 && ny > 0 && p[nx][ny]){
				v[p[i][j]].push_back(p[nx][ny]);
			}

			nx = i + 1, ny = j + 1;
			if (nx > 0 && ny > 0 && p[nx][ny]){
				v[p[i][j]].push_back(p[nx][ny]);
			}
		}
	}

	LL pre = 0;
	rep(i, 1, 21) pre = pre * 7LL + w[i];

	pre_dfs(1, 1, pre);

	scanf("%d", &T);
	while (T--){
		mp.clear();
		pos = 0;
		rep(i, 1, 21){
			scanf("%d", a + i);
			if (a[i] == 0){
				pos = i;
				a[i] = 6;
			}
		}

		LL st = 0;
		rep(i, 1, 21) st = st * 7LL + a[i];
		dfs(1, pos, st);
		ans = 1 << 30;

		bool fl = false;
		for (auto pppp : MP){
			LL ooo = pppp.first;
			if (mp[ooo] > 0){
				ans = min(ans, mp[ooo] - 1 + pppp.second - 1);
				fl = true;
			}
		}

		if (fl) printf("%d
", ans);
		else puts("too difficult");
	}

	return 0;
}

Problem 1002

比赛时并未想到，觉得这是一个近似的等比数列

然后一直在找公比是多少，然而并未找到

赛后才发现，最后要求的数列也存在递推关系

（可以用数学方法解出）

只要找出相应的系数即可

然后用矩阵快速幂进行计算

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<string>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #include<queue>
12 using namespace std;
13 typedef long long ll;
14 const ll mod=1e9+7;
15 int _;
16 struct matrix
17 {
18     ll a[2][2];
19     matrix()
20     {
21         a[0][0]=a[1][1]=1;
22         a[0][1]=a[1][0]=0;
23     }
24     matrix operator *(const matrix &b) const
25     {
26         matrix ret;
27         ret.a[0][0] = ( a[0][0] * b.a[0][0] %mod+ a[0][1] * b.a[1][0] %mod) % mod;
28         ret.a[0][1] = ( a[0][0] * b.a[0][1] %mod+ a[0][1] * b.a[1][1] %mod) % mod;
29         ret.a[1][0] = ( a[1][0] * b.a[0][0] %mod+ a[1][1] * b.a[1][0] %mod) % mod;
30         ret.a[1][1] = ( a[1][0] * b.a[0][1] %mod+ a[1][1] * b.a[1][1] %mod) % mod;
31         return ret;
32     }
33 } C;
34 matrix pow_mod(matrix a,ll b)
35 {
36     matrix ans;
37     while (b)
38     {
39         if (b&1) ans=ans*a;
40         b>>=1;
41         a=a*a;
42     }
43     return ans;
44 }
45 ll get(ll n)
46 {
47     if (n==0) return 0;
48     if (n==1) return 1;
49     return pow_mod(C,n-1).a[0][0];
50 }
51 int main()
52 {
53     C.a[0][0]=7;
54     C.a[0][1]=-4;
55     C.a[1][0]=1;
56     C.a[1][1]=0;
57     scanf("%d",&_);
58     while (_--)
59     {
60         ll n;
61         scanf("%lld",&n);
62         printf("%lld
",(get(n+1)-2*get(n)+mod*6)%mod);
63     }
64 }

View Code

Problem 1008

事实上，这是个最小点覆盖问题

设树上最大匹配数*2为tmp

如果k <tmp，那么答案为（k+1)/2

否则，答案为tmp/2+(k-tmp)

由于读入量大，还需要加人读入挂

  1 #include <bits/stdc++.h>
  2 
  3 namespace IO{
  4        const int MT = 50 * 1024 * 1024; 
  5        char IO_BUF[MT];
  6         int IO_PTR, IO_SZ;
  7     
  8         void begin(){
  9             IO_PTR = 0;
 10             IO_SZ = fread (IO_BUF, 1, MT, stdin);
 11         }
 12         template<typename T>
 13         inline bool scan_d (T & t){
 14             while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != '-' && (IO_BUF[IO_PTR] < '0' || IO_BUF[IO_PTR] > '9'))IO_PTR ++;
 15              if (IO_PTR >= IO_SZ) return false;
 16             bool sgn = false;
 17              if (IO_BUF[IO_PTR] == '-') sgn = true, IO_PTR ++;
 18             for (t = 0; IO_PTR < IO_SZ && '0' <= IO_BUF[IO_PTR] && IO_BUF[IO_PTR] <= '9'; IO_PTR ++)
 19                 t = t * 10 + IO_BUF[IO_PTR] - '0';
 20             if (sgn) t = -t;
 21             return true;
 22             
 23         }
 24         inline bool scan_s (char s[]){
 25                while (IO_PTR < IO_SZ && (IO_BUF[IO_PTR] == ' ' || IO_BUF[IO_PTR] == '
') ) IO_PTR ++;
 26             if (IO_PTR >= IO_SZ) return false;
 27             int len = 0;
 28             while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != ' ' && IO_BUF[IO_PTR] != '
')
 29                 s[len++] = IO_BUF[IO_PTR], IO_PTR ++;
 30             s[len] = '';
 31             return true;
 32         }
 33 };
 34 
 35 using namespace IO;
 36 
 37 using namespace std;
 38 
 39 #define rep(i, a, b)    for (int i(a); i <= (b); ++i)
 40 #define dec(i, a, b)    for (int i(a); i >= (b); --i)
 41 #define MP        make_pair
 42 #define fi        first
 43 #define se        second
 44 
 45 
 46 typedef long long LL;
 47 
 48 const int N = 100010;
 49 
 50 int T;
 51 int n, k;
 52 int f[N][3];
 53 vector <int> v[N];
 54 
 55 
 56 void dfs(int x){
 57     for (auto u : v[x]){
 58         dfs(u);
 59         int mx = max(f[u][0], f[u][1]);
 60         f[x][0] += mx;
 61     }
 62 
 63     for (auto u : v[x]){
 64         int t = f[x][0] - max(f[u][0], f[u][1]) + f[u][0] + 1;
 65         f[x][1] = max(f[x][1], t);
 66     }
 67 }
 68 
 69 int main(){
 70 
 71     IO::begin();
 72 
 73     scan_d(T);
 74     while (T--){
 75         scan_d(n);
 76         scan_d(k);
 77         rep(i, 0, n + 1) v[i].clear();
 78         memset(f, 0, sizeof f);
 79         rep(i, 2, n){
 80             int x;
 81             scan_d(x);
 82             v[x].push_back(i);
 83         }
 84         dfs(1);
 85 
 86         int tmp = max(f[1][0], f[1][1]);
 87         tmp *= 2;
 88 
 89 
 90         int ans;
 91         if (k <= tmp){
 92             ans = (k + 1) / 2;
 93         }
 94         else ans = tmp / 2 + (k - tmp);
 95 
 96         printf("%d
", ans);
 97             
 98 
 99 
100     }
101 
102     return 0;
103 }

View Code

Problem 1010

可以用set进行模拟

set的每个节点为pair

第一个存右节点，第二个存左节点

然后用lower_bound找到最合适的位置

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<string>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #include<queue>
12 using namespace std;
13 typedef long long ll;
14 const ll inf=(1<<31)-1;
15 multiset<pair<int,int> > s;
16 int n;
17 struct ss
18 {
19     int x,y;
20 };
21 ss a[100010];
22 int _;
23 inline bool cmp(ss a,ss b)
24 {
25     return a.x<b.x||(a.x==b.x&&a.y<b.y);
26 }
27 int main()
28 {
29     scanf("%d",&_);
30     while (_--)
31     {
32         s.clear();
33         scanf("%d",&n);
34         int i;
35         for (i=1;i<=n;i++)
36             scanf("%d%d",&a[i].x,&a[i].y);
37         sort(a+1,a+n+1,cmp);
38         s.insert({a[1].y,a[1].x});
39         multiset<pair<int,int> >::iterator iter;
40         for (i=2;i<=n;i++)
41         {
42             iter=s.lower_bound({a[i].x,inf});
43             if (iter!=s.begin()) iter--;
44             if (iter->first<=a[i].x)
45             {
46                 int x=iter->second;
47                 s.erase(iter);
48                 s.insert({a[i].y,x});
49                 //iter->first=a[i].y;
50             }
51             else
52                 s.insert({a[i].y,a[i].x});
53         }
54         ll ans=0;
55         for (auto u:s)
56         {
57             ans+=u.first-u.second;
58             //cout<<u.first<<" "<<u.second<<endl;
59         }
60         printf("%lu %lld
",s.size(),ans);
61     }
62     return 0;
63 }

View Code

Problem 1011

事实上就是一个求次短路问题
用dijstra求出次短路即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<string>
 8 #include<vector>
 9 #include<map>
10 #include<set>
11 #include<queue>
12 using namespace std;
13 typedef long long ll;
14 const ll inf=(1<<31)-1;
15 multiset<pair<int,int> > s;
16 int n;
17 struct ss
18 {
19     int x,y;
20 };
21 ss a[100010];
22 int _;
23 inline bool cmp(ss a,ss b)
24 {
25     return a.x<b.x||(a.x==b.x&&a.y<b.y);
26 }
27 int main()
28 {
29     scanf("%d",&_);
30     while (_--)
31     {
32         s.clear();
33         scanf("%d",&n);
34         int i;
35         for (i=1;i<=n;i++)
36             scanf("%d%d",&a[i].x,&a[i].y);
37         sort(a+1,a+n+1,cmp);
38         s.insert({a[1].y,a[1].x});
39         multiset<pair<int,int> >::iterator iter;
40         for (i=2;i<=n;i++)
41         {
42             iter=s.lower_bound({a[i].x,inf});
43             if (iter!=s.begin()) iter--;
44             if (iter->first<=a[i].x)
45             {
46                 int x=iter->second;
47                 s.erase(iter);
48                 s.insert({a[i].y,x});
49                 //iter->first=a[i].y;
50             }
51             else
52                 s.insert({a[i].y,a[i].x});
53         }
54         ll ans=0;
55         for (auto u:s)
56         {
57             ans+=u.first-u.second;
58             //cout<<u.first<<" "<<u.second<<endl;
59         }
60         printf("%lu %lld
",s.size(),ans);
61     }
62     return 0;
63 }

View Code