2019 Multi-University Training Contest 5
2019-08-06 / Luo Jinrong   

进度

A B C D E F G H I J
∅ √ √ √ √ ∅

1004. equation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define per(i, a, b) for(int i=a; i<b; i++)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

const int MAXN(1e5+7);
int T;
int outf;
struct nd{
    ll a, b;        // b/a
    inline void gui() {
        if(b==0) {
            a=1;
            return;
        }
        ll ff=1, ts;
        if(a*b<0) { ff = -1; }
        a = abs(a);
        b = abs(b);
        ts = gcd(a, b);
        a/=ts;
        b/=ts;
        b*=ff;
    }
    bool operator<(const nd& s) {
        return b*s.a<s.b*a;
    }
    bool operator==(const nd& s) {
        return (a*s.b==b*s.a);
    }
    bool operator>=(const nd& s) {
        return !(*this<s);
    }
}rln[MAXN], ln[MAXN];
ll N, C, cntt;
vector<nd> outt;
ll sa, sb;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--) {
        outf = 1;
        outt.clear();
        cin >> N >> C;
        per(i, 1, N+1) { cin >> rln[i].a >> rln[i].b; rln[i].b=-rln[i].b; }   //记录每条边的零点
        sort(rln+1, rln+1+N);
        //合并线
        cntt = 1;
        ln[cntt].a = rln[1].a; ln[cntt].b = rln[1].b;
        sa=-ln[1].a, sb=ln[1].b;
        per(i, 2, N+1) {
            sa -= rln[i].a; sb += rln[i].b;
            if(rln[i]==rln[i-1]) {
                ln[cntt].a += rln[i].a;
                ln[cntt].b += rln[i].b;
            } else {
                ln[++cntt].a = rln[i].a;
                ln[cntt].b = rln[i].b;
            }
        }
        N = cntt;
        nd tmp, llm, rlm=ln[1];
        if(sa==0) {
            if(sb==C) {
                cout << -1 << '\n';
                continue;
            }
        } else {
            tmp.b = C - sb;
            tmp.a = sa;
            tmp.gui();
            if (rlm >= tmp) outt.push_back(tmp);
        }
        per(i, 1, cntt) {
            llm = rlm;
            rlm = ln[i+1];
            sa += 2*ln[i].a;
            sb -= 2*ln[i].b;
            if(sa==0) {
                if(sb==C) {
                    outf = -1;
                    break;
                } else {
                    continue;
                }
            }
            tmp.b = C-sb;
            tmp.a = sa;
            tmp.gui();
            if(rlm>=tmp && llm<tmp) outt.push_back(tmp);
        }
        if(outf==-1) {
            cout << -1 << '\n';
            continue;
        }
        llm = rlm;
        sa += 2*ln[cntt].a;
        sb -= 2*ln[cntt].b;
        if(sa==0) {
            if(sb==C) {
                cout << -1 << '\n';
                continue;
            }
        } else {
            tmp.b = C - sb;
            tmp.a = sa;
            tmp.gui();
            if (llm < tmp) outt.push_back(tmp);
        }
        cout << outt.size();
        for(auto it: outt) {
            cout << ' ' << it.b << '/' << it.a;
        }
        cout << '\n';
    }

    return 0;
}

1005. permutation 1

题意

构造一个长度为n的数列a（1-n的排列），对于这个数列定义一个n-1长度的“差序列”p，其中p中每一项为a相邻两项之差，求字典序第k小的p所对应的数列a。

做法

因为所要求的k最大为10000，而8!>10000，则我们分两类进行讨论：

  • 当$n/leq 8$，枚举所有可能的排列，然后进行排序，在输出第k小的。
  • 当$n>8$，可固定前$n-8$位为$n,1,2,…,n-9$，然后用剩下的八个数枚举所有可能的排列，排序求第k小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
#define FIN freopen("./1005.in","r",stdin)
using namespace std;
typedef long long ll;
const int maxn(1e5+5);
int T,n,k,num,add[10],flag[10];
struct LIS{
    int l[10];
}lis[maxn];
set<int> s;
bool cmp(LIS l1,LIS l2){
    if(n>8){
        if(l1.l[0]!=l2.l[0]){
            return (l1.l[0])<(l2.l[0]);
        }
        for(int i=1;i<8;i++){
            if(l1.l[i]-l1.l[i-1]==l2.l[i]-l2.l[i-1]){
                continue;
            }else{
                return (l1.l[i]-l1.l[i-1])<(l2.l[i]-l2.l[i-1]);
            }
        }
    }else{
        for(int i=1;i<n;i++){
            if(l1.l[i]-l1.l[i-1]==l2.l[i]-l2.l[i-1]){
                continue;
            }else{
                return (l1.l[i]-l1.l[i-1])<(l2.l[i]-l2.l[i-1]);
            }
        }
    }
    return true;
}
void dfs(int nn,int l[]){
    if(n>8&&nn==8){
        for(int i=0;i<8;i++){
            lis[num].l[i]=l[i];
        }
        num++;
    }else if(n<=8&&nn==n){
        for(int i=0;i<n;i++){
            lis[num].l[i]=l[i];
        }
        num++;
    }
    int len=(n>8?8:n);
    for(int i=0;i<len;i++){
        if(!flag[i]){
            flag[i]=1;
            l[nn]=add[i];
            dfs(nn+1,l);
            flag[i]=0;
        }
    }
}
int main(){
#ifndef ONLINE_JUDGE
    FIN;
#endif
    cin>>T;
    for(int t=1;t<=T;t++){
        num=0;
        cin>>n>>k;
        if(n>8){
            cout<<n<<" ";
            for(int i=1;i<n-8;i++){
                cout<<i<<" ";
            }
            for(int i=n-8;i<n;i++){
                add[i-n+8]=i;
                flag[i-n+8]=0;
            }
            int l[10];
            dfs(0,l);
        }else{
            for(int i=1;i<=n;i++){
                add[i-1]=i;
                flag[i-1]=0;
            }
            int l[10];
            dfs(0,l);
        }
        sort(lis,lis+num,cmp);
        //cout<<num<<endl;
        if(n>8){
            for(int i=0;i<8;i++){
                cout<<lis[k-1].l[i]<<" \n"[i==7];
            }
        }else{
            for(int i=0;i<n;i++){
                cout<<lis[k-1].l[i]<<" \n"[i==n-1];
            }
        }
    }
}

1006. string matching

题意

给定一个字符串s，有一个暴搜方法，可以求出s所有后缀（不包含s）与s的最长公共前缀，求这个算法共需比较几次。

做法

  • 扩展KMP模板题
  • 套模板求出每个后缀与s最长公共前缀的长度存在next数组里面
  • 最后答案就是next数组求和，并且如果该后缀不是s的前缀时再+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#define FIN freopen("./1006.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e6+5);
ll T,n,nextt[maxn],ans;
char s[maxn];
void getNext(char *s,ll nextt[]){
    ll nn = strlen(s);
    nextt[0] = nn;
    ll p = 0;
    while (p+1 < nn && s[p] == s[p+1]) p++;
    nextt[1] = p;
    ll k = 1, L;
    for (ll i = 2; i < nn; i++){
        p =     k + nextt[k] - 1; L = nextt[i - k];
        if (i + L <= p) nextt[i] = L;
        else {
            ll j = p - i + 1;
            if (j < 0) j = 0;
            while (i + j < nn && s[i + j] == s[j]) j++;
            nextt[i] = j; k = i;

        }
    }
//    for (int i=0;i<nn;i++){
//        cout<< nextt[i] <<" ";
//    }cout<<endl;
}
int main(){
#ifndef ONLINE_JUDGE
    FIN;
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    for(int t=1;t<=T;t++){
        ans=0;
        cin>>s;
        n=strlen(s);
        getNext(s,nextt);
        for(ll i=1;i<n;i++){
            ans+=1+nextt[i];
            if(nextt[i]+i==n){
                ans--;
            }
        }
        cout<<ans<<"\n";
    }
}

1007. permutation 2

题意

构造一个长度为n的数列a（1-n的排列），并且规定第1位为x，第n位为y，对于a数组的每个元素，与其相邻元素的差不大于2，求能构造出的数列a的数量。

做法

  • 首先关注特殊情况，当$x=1,y=n$，设数列ａ的数量为$f(n)$

$$
f(n)=\begin{cases}
1,1\leq n\leq 3\\
f(n-1)+f(n-3),n\geq 4
\end{cases}
$$

  • 对于一般情况，左半部分一定是$x->1->x+1$，右半部分一定是$y->n->y-1$，且只有一种方法，对于中间部分，则又可以转化为特殊情况的样子做，也就是求$f(y-1-x)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#pragma warning(disable:4996)

#include<bits/stdc++.h>
#define upf(a,b,c) for(ll a=b;a<=c;++a)
#define drf(a,b,c) for(ll a=b;a>=c;--a)
#define ll long long
#define mod MOD
const int MOD(998244353);
const double esp(1e-6);
const int maxn(1024 * 1024 + 5);
using namespace std;
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a % mod; a = a * a % mod; }return res; }
ll T, n, k, N, inv2;
ll a[maxn];
ll C(ll i, ll m) {
    ll sum = 1;
    upf(j, m, m - i + 1) {
        sum *= j;
        sum %= mod;
    }
    upf(j, 1, i) {
        sum *= powmod(j, mod - 2);
        sum %= mod;
    }
    return sum;
}
ll dp[maxn];
int main() {
#ifdef ACM_LOCAL
    freopen("./ACM.in", "r", stdin);
    freopen("./ACM.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll x, y;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    upf(i, 4, 100000) {
        dp[i] = dp[i - 1] + dp[i - 3];
        dp[i] %= mod;
    }
    cin >> T;
    while (T--) {
        cin >> N >> x >> y;
        if (x != 1)
            x++;
        if (y != N)
            y--;
        N = y - x + 1;
        cout << dp[N] << endl;
    }
}

1008. line symmetric

题意

平面上有n个点，按顺序输入组成一个n边形，问能否至多只移动一个点，使得该图形变成一个轴对称图形，移动点不能与其他点重合。

做法

  • 如果一个多边形是轴对称图形，则其对称轴一定在相邻顶点或有公共相邻顶点的两顶点的连线的中垂线上。
  • 枚举两相邻顶点i,i+1和有公共相邻顶点的两顶点i,i+2，求出这两个点的中垂线
  • 然后i往小遍历，i+1/i+2往大遍历，依次判断相应点是否关于上述中垂线对称
  • 只有当不对称的顶点不大于1对时才有可能满足题意
  • 而当不对称顶点只有一对，还要保证两点必须有一点跟对应的i,i+1/i+2在对称轴同侧，如下图

  • 这种情况下移动一个顶点只能变成如下情况

  • 这样得到的多边形虽然是轴对称，但是不满足题中的简单多边形。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
#define FIN freopen("./1008.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e3+5);
const double eps(1e-8);
ll T,n,a[maxn];
double k,b;
struct point{
	double x,y;
}p[maxn];
double dis(point p1,point p2){//两点距离
	return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
bool match(int p1,int p2){//两点是否关于y=kx+b对称
	point tmp;
	tmp.y=(k*p[p1].x+k*k*p[p1].y+k*p[p1].x+2*b-p[p1].y)/(1+k*k);
	tmp.x=p[p1].x-k*tmp.y+k*p[p1].y;
	if(dis(tmp,p[p2])<eps){
		return true;
	}
	return false;
}
bool check(int p1,int p2){//以p1,p2的中垂线为对称轴
	k=(p[p1].x-p[p2].x)/(p[p2].y-p[p1].y);
	b=(p[p1].y+p[p2].y)/2-k*(p[p1].x+p[p2].x)/2;
	int nm=0;
	if(((p1+2)%n==p2)&&(!match((p1+1)%n,(p2-1+n)%n))){//p1p2相隔的那个点是否在对称轴上
		nm++;
	}
	int len=((p1+1)%n==p2)?((n+1)/2-1):((n-2)/2);
	for(int i=1;i<=len;i++){//对称轴两侧枚举相应点
		if(!match((p1-i+n)%n,(p2+i)%n)){
			nm++;
			if(((k*p[(p1-i+n)%n].x+b-p[(p1-i+n)%n].y)*(k*p[p1].x+b-p[p1].y)<eps)&&((k*p[(p2+i)%n].x+b-p[(p2+i)%n].y)*(k*p[p2].x+b-p[p2].y)<eps)){//两点必须保证有一点跟对应的p1p2在对称轴同侧
				nm++;
			}
			if(nm>1){
				break;
			}
		}
	}
	if(nm<=1){
		return true;
	}
	return false;
}
bool solve(){
	if(n<=4){
		return true;
	}
	for(int i=0;i<n;i++){
		if(check(i,(i+1)%n)){//枚举相邻点
			return true;
		}
		if(check(i,(i+2)%n)){
			return true;
		}
	}
	return false;
}
int main(){
#ifndef ONLINE_JUDGE
	FIN;
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	for(int t=1;t<=T;t++){
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>p[i].x>>p[i].y;
		}
		cout<<(solve()?"Y\n":"N\n");
	}
}

return 0;

本文链接：
https://luojinrong.github.io/2019/08/06/2019-Multi-University-Training-Contest-5/