Team Round #1: ICPC Central Russia Regional Contest

发表于 分类于 阅读次数： 评论数：
本文字数： 676 阅读时长 ≈ 2 分钟
本文记录了金陵香辣烤虾仁闷骚牛肉鸭饭的第??场训练

传送门

A

Description

两杯水混合温度80，求两杯水体积。

Solution

观察到数据很小，暴力枚举。有特判。。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
    int t1 , t2;
    cin >> t1 >> t2;
    if(t1 == 80){
        cout << "1 0" << endl;
        return 0;
    }
    if(t2 == 80) {
        cout << "0 1" << endl;
        return 0;
    }
    for(int v1 = 1; v1 <= 1000; v1++){
        for(int v2 = 1; v2 <= 1000; v2++){
            if(t1 * v1 + t2 * v2 == 80 * (v1 + v2)){
                cout << v1 << " " << v2 << endl;
                return 0;
            }
        }
    }    
    return 0;
}

B

Description

电路电阻。

Solution

发现单调性。二分一下。

Code

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
int n , R, r[maxn];
double chk(double x){
    double res = 0;
    for(int i = 1; i <= n; i++) {
        res += (r[i] * x) / (r[i] + x);
    }
    return res;
}
int main()
{
    // close;
    cin >> n >> R;
    for(int i = 1; i <= n; i++){
        // cin >> r[i];
        read(r[i]);
    }
    double le = 0, ri = INF;
    for(int i = 1; i <= 100; i++){
        double mid = (le + ri) / 2.0; 
        if(chk(mid) > R){
            ri = mid;
        }else {
            le = mid;
        }
    }
    printf("%.8f\n", le);
    return 0;
}

C

Description

没看

Solution

听说是模拟

Code

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#define endl '\n'
int mp[1000];
char s[11000];
int main() {
    scanf("%s", s+1); int len = strlen(s+1);
    for(int i = 1; i <= len; i++) mp[s[i]]++;
    //[:|||:]
    if(mp['[']) {
        int tp = mp['['];
        for(int i = 1; i <= tp; i++) {
            //cout << R"([:|||:])" << endl;
            puts("[:|||:]");
            mp['[']--; mp[']']--; mp[':'] -= 2; mp['|'] -= 3;
        }
    }
    //:-|
    if(mp['|']) {
        int tp = mp['|'];
        for(int i = 1; i <= tp; i++) {
            //cout << R"(:-|)" << endl;
            puts(":-|");
            mp[':']--; mp['-']--; mp['|']--;
        }
    }
    //:~(
    if(mp['~']) {
        int tp = mp['~'];
        for(int i = 1; i <= tp; i++) {
            //cout << R"(:~()" << endl;
            puts(":~(");
            mp[':']--; mp['~']--; mp['(']--;
        }
    }
    //:-X
    if(mp['X']) {
        int tp = mp['X'];
        for(int i = 1; i <= tp; i++) {
            //cout << R"(:-X)" << endl;
            puts(":-X");
            mp[':']--; mp['-']--; mp['X']--;
        }
    }
    //%0
    if(mp['%']) {
        int tp = mp['%'];
        for(int i = 1; i <= tp; i++) {
            //cout << R"(%0)" << endl;
            puts("%0");
            mp['0']--; mp['%']--;
        }
    }
    //8-0
    if(mp['8']) {
        int tp = mp['8'];
        for(int i = 1; i <= tp; i++) {
            //cout << R"(8-0)" << endl;
            puts("8-0");
            mp['0']--; mp['8']--; mp['-']--;
        }
    }
    //:-E
    if(mp['E']) {
        int tp = mp['E'];
        for(int i = 1; i <= tp; i++) {
            //cout << R"(:-E)" << endl;
            puts(":-E");
            mp[':']--; mp['-']--; mp['E']--;
        }
    }
    //:-0
    if(mp['0']) {
        int tp = mp['0'];
        for(int i = 1; i <= tp; i++) {
            //cout << R"(:-0)" << endl;
            puts(":-0");
            mp[':']--; mp['-']--; mp['0']--;
        }
    }
    //:C
    if(mp['C']) {
        int tp = mp['C'];
        for(int i = 1; i <= tp; i++) {
            //cout << R"(:C)" << endl;
            puts(":C");
            mp[':']--; mp['C']--;
        }
    }
    //:D
    if(mp['D']) {
        int tp = mp['D'];
        for(int i = 1; i <= tp; i++) {
            //cout << R"(:D)" << endl;
            puts(":D");
            mp[':']--; mp['D']--;;
        }
    }
    //:-P
    if(mp['P']) {
        int tp = mp['P'];
        for(int i = 1; i <= tp; i++) {
            //cout << R"(:-P)" << endl;
            puts(":-P");
            mp[':']--; mp['P']--; mp['-']--;
        }
    }

    if(mp['\\']) {
        int tp = mp['\\'];
        for(int i = 1; i <= tp; i++) {
            //cout << R"(:-\)" << endl;
            puts(":-\\");
            mp['\\']--; mp['-']--; mp[':']--;
        }
    }
    while(mp[';']) {
        if(mp['(']) {
            //cout << R"(;-()" << endl,
            puts(";-("), mp[';']--, mp['-']--, mp['(']--;
            continue;
        }
        if(mp[')']) {
            //cout << R"(;-))" << endl,
            puts(";-)"), mp[';']--, mp['-']--, mp[')']--;
            continue;
        }
    }
    while(mp[':']) {
        if(mp[')']) {
            //:)
            //cout << R"(:))" << endl,
            puts(":)"), mp[':']--, mp[')']--;
            continue;
        }
        if(mp['(']) {
            //:(
            //cout << R"(:()" << endl,
            puts(":("), mp[':']--, mp['(']--;
            continue;
        }
    }
    //cout << "LOL" << endl;
    puts("LOL");
    return 0;
}

D

Description

给定a,b，求$a^x==x^b$时候的x。

Solution

多校Claris有个题有个思想，拿三个素数check，maxn不能开太大，会TLE。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
    int a , b;
    cin >> a >> b;
    vi pri;
    pri.eb(P_1), pri.eb(P_2), pri.eb(Erica);
    for(int i = 1; i < maxn; i++){
        int fl = 1;
        for(auto it : pri){
            if(bin(a, i , it) != bin(i, b , it)) {
                fl = 0;
            }
        }
        if(fl) {
            cout << i << endl;
            return 0;
        }
    }
    cout << 0 << endl;
    return 0;
}

E

Description

Solution

待补（gugu）

Code

F

Description

取一个或两个或全部字符，最后一次操作的人获胜。

Solution

记忆化搜索。

Code

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
#include <bits/stdc++.h>
using namespace std;
string s;
map<multiset<int>, int> mp;
multiset<int> st;
int dfs() {
    if(st.size() == 1) return true;
    if(mp.count(st)) return mp[st];
    vector<int> sg, v;
    for(auto x : st) v.push_back(x);
    for(auto x : v) {
        if(x) {
            st.erase(st.find(x)); st.insert(x-1);
            sg.push_back(dfs()); st.erase(st.find(x-1)); st.insert(x);
        }
        if(x >= 2) {
            st.erase(st.find(x)); st.insert(x-2);
            sg.push_back(dfs()); st.erase(st.find(x-2)); st.insert(x);
        }
        if(x > 2) {
            st.erase(st.find(x)); sg.push_back(dfs()); st.insert(x);
        }

    }
    int flag = 0;
    for(auto x : sg)
        if(x == 0) flag = 1;
    return mp[st] = flag;
}
bool doit() {
    mp.clear();
    cin >> s;
    vector<int> a(30, 0);
    for(auto x : s) a[x-'A']++;
    for(int i = 0; i < 26; i++) st.insert(a[i]);
    if(dfs() == 1) cout << "Alice";
    else cout << "Bob";
}
int main() {
    doit();
    //st.insert(4); st.insert(4); st.insert(4); st.insert(4);
    //st.insert(4); st.insert(4); st.insert(4);
    //cout << dfs();
    return 0;
}
//AAAAAAAAAAAAAAAAAAAABBBBBBBBCCCCCCCDDDDD

别人的代码。不明白啊qwq。。得补补吧呜呜。

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>
using namespace std;

const int N = 50;
int sg[N];

int main(void) {
    for (int i = 1; i < N; ++i)
        sg[i] = i % 3 + (i % 3 == 0 ? 3 : 0);

    int c[26] = { 0 };
    string s; cin >> s;
    for (char ch : s)
        c[ch - 'A']++;
    
    int ans = 0;
    for (int i = 0; i < 26; ++i)
        if (c[i])
            ans ^= sg[c[i]];
    
    printf("%s\n", ans == 0 ? "Bob" : "Alice");

    return 0;
}

G

Description

Solution

待补

Code

H

Description

签到

Solution

签到

Code

1
2
3
4
5
6
7
int main()
{
    int n;
    cin >> n ;
    cout << (n & 1 ? 2 : 1) << endl;
    return 0;
}

I

Description

Solution

待补

Code

J

Description

$k(k\le 5)$个数使得${a_1}^{3}+\cdots {a_k}^3=x(x\le 10^{100000})$，构造出来。

Solution

观察到k很小，然后用$(x-1)^3,(x+1)^3$展开后发现和为$2x^3+6x$,那么用两个-x抵一下，然后分类对mod  6讨论一下。

Code

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
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        BigInteger Erica = BigInteger.valueOf(6);
        BigInteger ONE = BigInteger.ONE;
        BigInteger FU = BigInteger.valueOf(-1);
        BigInteger x = cin.nextBigInteger();
        BigInteger modd = x.mod(Erica);
        if(modd.equals(BigInteger.valueOf(0))){
            System.out.println(4);
            BigInteger xx = x.divide(Erica);
            System.out.println(xx.multiply(FU)+ " " + xx.multiply(FU) + " " + xx.add(ONE) + " "+ xx.subtract(ONE));
            return ;
        }
        if(modd.equals(ONE)){
            System.out.println(5);
            BigInteger xx = (x.subtract(ONE)).divide(Erica);
            System.out.println("1 "+xx.subtract(ONE)+" " + xx.add(ONE) + " " + xx.multiply(FU) + " " + xx.multiply(FU));
            return ;
        }
        if(modd.equals(BigInteger.valueOf(2))){
            System.out.println(5);
            BigInteger xx = (x.subtract(BigInteger.valueOf(8))).divide(Erica);
            System.out.println("2 "+xx.subtract(ONE)+" " + xx.add(ONE) + " " + xx.multiply(FU) + " " + xx.multiply(FU));
            return ;
        }
        if(modd.equals(BigInteger.valueOf(3))){
            System.out.println(5);
            BigInteger xx = (x.add(BigInteger.valueOf(27))).divide(Erica);
            System.out.println("-3 "+xx.subtract(ONE)+" " + xx.add(ONE) + " " + xx.multiply(FU) + " " + xx.multiply(FU));
            return ;
        }
        if(modd.equals(BigInteger.valueOf(4))){
            System.out.println(5);
            BigInteger xx = (x.add(BigInteger.valueOf(8))).divide(Erica);
            System.out.println("-2 "+xx.subtract(ONE)+" " + xx.add(ONE) + " " + xx.multiply(FU) + " " + xx.multiply(FU));
            return ;
        }
        if(modd.equals(BigInteger.valueOf(5))) {
            System.out.println(5);
            BigInteger xx = (x.add(ONE)).divide(Erica);
            System.out.println("-1 "+xx.subtract(ONE)+" " + xx.add(ONE) + " " + xx.multiply(FU) + " " + xx.multiply(FU));
            return ;
        }
    }
}

K

Description

两两交换相邻的数字，使得数字前一段下降，后一段上升。数字两两不同。

Solution

发现最大数字要么最左边要么最右边，然后次大数字，模拟这个过程，Fenwick tree维护一下。

Code

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
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define IN freopen("in.txt", "r", stdin);
#define OUT freopen("out.txt","w",stdout);
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;

const int N = 1e5+10;
int al[N],len,a[N];

int s[N];
#define lowb(x) (x&-x)
void add(int x,int num){
    for(;x<N;x+=lowb(x))s[x]+=num;
}
int query(int x){
    int res=0;
    for(;x;x-=lowb(x))res+=s[x];
    return res;
}

int find(int x){
    return lower_bound(al+1,al+1+len,x)-al;
}
int pos[N];

int main(){
//    IN;
    IOS;
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],al[++len]=a[i];
    sort(al+1,al+1+len);
    for(int i=1;i<=n;i++){
        a[i]=find(a[i]);
        pos[a[i]]=i;
        add(i,1);
    }
    ll ans=0;
    for(int i=n;i;i--){
        int p=pos[i];
        ans+=min(query(p-1),query(n)-query(p));
        add(p,-1);
    }
    cout<<ans<<endl;
    return 0;
}
-------------本文结束感谢您的阅读-------------