Team Round #4:2017 JUST Programming Contest 2.0

发表于 更新于 分类于 阅读次数： 评论数：
本文字数： 765 阅读时长 ≈ 3 分钟
本文记录了Daenerys Stormborn of the House Targaryen.的第04场训练

Team Round(Training)系列：每周六12：15-17：15

这场比赛是在9月28日13：30 - 16：30打的，原标题为GYM#4 信心恢复训练（cloned from cls）

PS：LM在原先的比赛中是没有的，我随便找了div1的bc题，但是后面也没有去攻破他们。

信心恢复场嘛，做的题就会多一些，一共解了DIHGEFCKB九道题目

D - Husam’s Bug

题解：模拟

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
// Author : Wqr_
// Time : 19/09/28
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ttl(x) cout << "#" << (x) << "#" << endl;
#define ttt(x) cout << "#" << (x) << "#";
#define ttn cout << "####" << endl;
using namespace std;
typedef long long ll;
int main(){
    int n;
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    string in;
    for(int i = 0; i < n; i++){
        cin >> in;
        int cs = 0;
        int di = 0;
        int sy = 0;
        int l = in.length();
        for(int i = 0; i < l; i++){
            if(isalpha(in[i])) cs++;
            if(isdigit(in[i])) di++;
            if(ispunct(in[i])) sy++;
        }
        if(cs < 4){
            cout << "The last character must be a letter." << endl;
        }else if(di < 4){
            cout << "The last character must be a digit." << endl;
        }else if(sy < 2){
            cout << "The last character must be a symbol." << endl;
        }else{
            cout << "The last character can be any type." << endl;
        }
        cs = 0;
        di = 0;
        sy = 0;
    }
    return 0;
}

I - Husam and the Broken Present 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
/************************************************
 # @Author:      miniLCT
 # @DateTime:    2019-09-28 13:58:53
 # @Description: You build it.You run it
 # @More: If lots of AC,try BF,dfs,DP
 ***********************************************/
#include <bits/stdc++.h>

using namespace std;
#define eps 1e-8
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 1e6;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
int n ;
int a[105][105];
int b[maxn];
int main()
{
    cin >> n;
    for(int i = 0; i < n;i++){
        for(int j = 0; j < n;j++){
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < n;i++){
        b[i] = sqrt(a[i][i]);
    }
    for(int i = 0; i < n;i++){
        cout << b[i] <<' ';
    }

}

/******************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*******************************************************/

H - Give Me This Pizza

题解：单调栈经典问题？(dqy写的)

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
#include <bits/stdc++.h>
using namespace std;
//fdsfsaddgsadfkolahsduoibkjsadngflksadbgildsabnkijgasbkjlgb
//dfnkjasdbfijkasnbdlkfnsa
//nfolkjshfdkibsadkljf
//dnsojkfnkjsadfbksadbgl
typedef pair<int, int> pii;
const int maxn = 1e5+10;

stack<pii> s;
int a[maxn], b[maxn];
#define fi first
int main(){
    int n;
    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    for(int i = 0; i < n; i++){
        if(s.empty()){
            s.push({a[i], i});
        }else{
            while (!s.empty()){
                int tmp = s.top().fi;
                if(tmp >= a[i]){
                    s.push({a[i], i});
                    break;
                }else{
                    b[s.top().second] = a[i];
                    s.pop();
                    if(s.empty()) s.push({a[i], i});
                }
            }
        }
    }
    while (!s.empty()){
        b[s.top().second] = -1;
        s.pop();
    }
    for(int i = 0; i < n; i++){
        cout<<b[i]<<' ';
    }
    return 0;
}

G - In the Chairman’s office

题解：可怕的是我当时wa 了两发？？

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
/************************************************
 # @Author:      miniLCT
 # @DateTime:    2019-09-28 14:15:21
 # @Description: You build it.You run it
 # @More: If lots of AC,try BF,dfs,DP
 ***********************************************/
#include <bits/stdc++.h>

using namespace std;
#define eps 1e-8
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 1e6;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
int main()
{
	int n , m ;
	cin >> n >> m;
	/*if(n == 1){
		cout << "YES" << endl;
		return 0;
	}
	if(__gcd(n,m) == 1 || n > m)cout << "NO" << endl;
	else cout << "YES" <<endl;*/
	if(m/n*n==m)cout << "YES" <<endl;
	else cout << "NO" <<endl;
}

/******************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*******************************************************/

E - Abdalrahman Ali Bugs

题解：枚举

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
/****************************************************************
 # @Author:      miniLCT
 # @DateTime: 2019年09月28日 星期六 14时44分34秒
 # @Description: You build it. You run it 
 # @More: Once lots of AC, try Brute-force,dynamic programming 
 ****************************************************************/
#include<bits/stdc++.h>

using namespace std;
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define eps 1e-8
#define int long long 
typedef long long ll;
const int maxn = 1e6;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
int a[26];
int32_t main(){
    close;
    string s;
    cin >> s;
    int len = s.length();
    for(int i = 0; i < len;i++){
        a[s[i]-'a']++;
    }
    int ans = 2;
    ll min = 1e18;
    for(int i = 2; i <= 100000;i++){
        ll cnt = 0;
        for(int j = 0; j < 26;j++){
            cnt += a[j]*(a[j]%i)*a[j];
        }
        if(cnt < min){
            min = cnt;
            ans = i;
        }
    }
    cout << ans << endl;

    return 0;
}

/*****************************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*****************************************************************/

F - Certifications

二分

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
// Author : Wqr_
// Time : 19/09/28
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ttl(x) cout << "#" << (x) << "#" << endl;
#define ttt(x) cout << "#" << (x) << "#";
#define ttn cout << "####" << endl;
using namespace std;
typedef long long ll;
const int nmax = 1e5 + 10;
int n, m, a[nmax], x[nmax];
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a, a + n);
    cin >> m;
    int in;
    for(int i = 0; i < m; i++){
        cin >> in;
        int it = lower_bound(a, a + n, in) - a;
        if(it != n){
            cout << a[it] << endl;
        }else{
            cout << "Dr. Samer cannot take any offer :(." << endl;
        }
    }
    return 0;
}

C - MRT Map

题解：dqy写的最短路…甚至没看题

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e4+10;

char a[maxn][30];

const int INF = 0x3f3f3f3f;
const int MAXN = 1e6+10;

struct qnode{
    int v;
    int c;
    qnode(int _v = 0, int _c = 0): v(_v), c(_c){}
    bool operator <(const qnode &r) const {
        return c > r.c;
    }
};

struct Edge{
    int v, cost;
    Edge(int _v = 0, int _cost = 0):v(_v), cost(_cost){}
};

vector<Edge> E[MAXN];
bool vis[MAXN];
int dist[MAXN];

void Dijkstra(int n, int start){
    memset(vis, false, sizeof(vis));
    for(int i = 1; i <= n; i++) dist[i] = INF;
    priority_queue<qnode> que;
    while (!que.empty())que.pop();
    dist[start] = 0;
    que.push(qnode(start, 0));
    qnode tmp;
    while (!que.empty()){
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if(vis[u])continue;
        vis[u] = true;
        for(int i = 0; i < E[u].size(); i++){
            int v = E[tmp.v][i].v;
            int cost = E[u][i].cost;
            if(!vis[v]&&dist[v]>dist[u]+cost){
                dist[v] = dist[u]+cost;
                que.push(qnode(v, dist[v]));
            }
        }
    }
}
void addedge(int u, int v, int w){
    E[u].push_back(Edge(v, w));
}

int xx[30], yy[30];

int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < 30; j++){
            xx[j] = yy[j] = 0;
        }
        int x, y;
        cin >> x >> y;
        int len1 = strlen(a[x]), len2 = strlen(a[y]);
        for(int j = 0; j < len1; j++){
            char s = a[x][j];
            if(s > 'Z') s-=32;
            xx[s-'A']++;
        }
        for(int j = 0; j < len2; j++){
            char s = a[y][j];
            if(s > 'Z') s-=32;
            yy[s-'A']++;
        }
        int res = 0;
        for(int j = 0; j < 30; j++){
            if(xx[j]&&yy[j])res++;
        }
        addedge(x, y, res);
        addedge(y, x, res);
    }
    int s, e; cin>>s>>e;
    Dijkstra(n, s);
    cout<<dist[e];
    return 0;
}

K - Counting Time

题意：给一个九宫格的初始状态 填完这个九宫格使得每个数字x能跳到x+1的方案有多少种 能跳到的区域为八连通 且x只能跳到x+1

题解：dfs

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
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
char a[5][5];
int b[5][5];
int vis[15];
map<int, int> msk;
vector<pii> vec;

int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {0,1,-1,1,-1,1,-1,0};

int ans = 0;
void dfs(int x){
    if(x == vec.size()){
        bool dj = 0;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(b[i][j] == 9)continue;
                bool f = 0;
                for(int z = 0; z < 8; z++){
                    int xx = i+dx[z], yy = j+dy[z];
                    if(xx<0 || xx>=3 || yy<0 || yy>=3)continue;
                    else{
                        if(b[xx][yy] == b[i][j]+1)f=true;
                    }
                }
                if(!f) dj = 1;
            }
        }
        if(!dj)ans++;
    }
    for(int i = 1; i <= 9; i++){
        if(vis[i]) continue;
        else{
            vis[i]++;
            b[vec[x].first][vec[x].second] = i;
            dfs(x+1);
            vis[i]--;
        }
    }
}

int main(){
    for(int i = 0; i < 3; i++){
        cin>>a[i];
        for(int j = 0; j < 3; j++){
            if(a[i][j]!='0') vis[a[i][j]-'0']++;
            else vec.push_back({i,j});
            b[i][j] = a[i][j]-'0';
        }
    }
    dfs(0);
    cout<<ans;
    return 0;
}

B - So You Think You Can Count?

题意：把一个字符串分成若干段，每一段里面的字符不能重复，问有多少种分法

题解： 动态规划，定义dp 表示字符串前n个字母的分法种数，先预处理字符串，对于每个字符，计算出以这个字符为结尾的无重复字符的一段最长的长度，第i个字符对应的长度记为f[i]然后可以得出递推式：dp[0]=1;dp[i]=dp[i-j] (1<=j<=10)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define  int long long
using namespace std;
const int maxn = 1e6+100;
const int mod = 1000*1000*1000+7;
char str[maxn];int vis[10];int dp[maxn];
int32_t main(){
    int n;
    cin >> n;
    scanf("%s",str+1);
    //cout << str <<endl;
    dp[0] = 1;
    for(int i = 1; i <= n;i++){
        memset(vis,0, sizeof(vis));
        for(int j = i;j >= 1;j--){
            if(vis[str[j] - '0'])break;
            else {
                vis[str[j] - '0'] = 1;
                dp[i] = (dp[i] + dp[j-1]) % mod;
            }
        }
    }
    cout << dp[n] << endl;
}

补题：

A - On The Way to Lucky Plaza

题意：m个店 每个店可以买一个小球的概率为p 求恰好在第m个店买到k个小球的概率
思路：概率dp，利用了线性性。第i个店买到第k1个球是 由 第i-1个点买了k1-1个球乘p得到。两个点：逆元用一下，存在精度问题。
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
#include <bits/stdc++.h>

#define int long long
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
using namespace std;
using ll = long long;
const int mod = 1e9+7;
const int maxn = 1e5+10;
const double eps = 1e-8;
int n, m ,k ,inv[maxn];
double p;
int pow_mod(int x, int y){
    int res = 1;
    while(y){
        if(y & 1)res = res * x % mod;
        x = x*x%mod;
        y >>= 1;
    }
    return res % mod;
}
void init(){
    for(int i = 1; i < maxn;i++)
        inv[i] = pow_mod(i , mod - 2);
}
int32_t main(){
    cin >> m >> n >> k;
    init();
    cin >> p;
    ll P = (ll)(1000*p+eps);
    ll ans = 1;
    FOR(i ,1 , k)ans = ans * inv[i] % mod * (n-i) %mod;
    FOR(i,1,k+1)ans = ans * P % mod;
    FOR(i,1,n-k+1)ans = ans*(1000-P)%mod;
    FOR(i,1,n+1)ans=ans*inv[1000]%mod;
    cout << ans << endl;
}
-------------本文结束感谢您的阅读-------------