2018中国大学生程序设计竞赛 - 网络选拔赛

Posted on | In , | Visitors:

补题！

补题： 3+3题/9题

A. Buy and Resell

每一次找前面最小的，用优先队列维护。同时若是这次买的是上次卖的，则可以合二为一。用map记录了一下卖的记录。

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 <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
priority_queue<int,vector<int>,greater<int> >q;
map<int,int>sell;
int n,x,y;
ll ans,times;
void init(){
    while(!q.empty()) q.pop();
    ans=times=0;
    sell.clear();
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        init();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            if(q.empty()||q.top()>=x) q.push(x);
            else{
                y=q.top();q.pop();
                ans+=(x-y);
                if(sell[y]){
                    sell[y]--;
                    sell[x]++;
                    q.push(y);
                    q.push(x);
                }else{
                    q.push(x);
                    sell[x]++;
                    times+=2;
                }
            }
        }
        printf("%lld %lld\n",ans,times);
    }
    return 0;
}

B. Congruence equation(不会啊)

C. Dream

根据费马小定理得(m+n)^{p−1}≡1(mod p)

因此，(m+n)^p≡m+n (mod p)

同时，m^p+n^p≡m+n (mod p)

所以，(m+n)^p=m^p+n^p(0≤m,n<p)恒成立，且加法运算与乘法运算封闭。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include <cstdio>
using namespace std;
const int maxn =1e5+5;
int p;
int main(){
    int T; scanf("%d",&T);
    while(T--){
        scanf("%d",&p);
        for(int i=0;i<p;++i){
            for(int j=0;j<p;++j){
                printf("%d%c",(i+j)%p,j==p-1?'\n':' ');
            }
        }
        for(int i=0;i<p;++i){
            for(int j=0;j<p;++j){
                printf("%d%c",(i*j%p),j==p-1?'\n':' ');
            }
        }
    }
    return 0;
}

D. Integer

注意一个坑点，找到(c-b)的值后，可能计算出的c的值会超出范围

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxx=1e9;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        ll n, a;
        scanf("%lld%lld",&n,&a);
        if(n > 2)
            printf("-1 -1\n");
        else if(n == 0)
            printf("-1 -1\n");
        else if(n == 1)
            printf("1 %lld\n",a+1);
        else{
            int flag = 0;
            ll tmp = a*a;
            for(ll i=1; i<a; i++){
                if(tmp % i == 0){
                    ll yu = tmp / i;
                    ll imax = yu;
                    ll imin = i;
                    ll cha = imax - imin;
                    if(cha % 2 == 0){
                        ll b = (imax - imin) / 2;
                        ll c = imax - b;
                        if(b>maxx||c>maxx||b<1||c<1) continue;
                        flag = 1;
                        printf("%lld %lld\n",b, c);
                        break;
                    }
                }
            }
            if(flag == 0)
                printf("-1 -1\n");
        }
    }
    return 0;
}

E. GuGu Convolution(不会啊)

F. Neko and Inu(不会啊)

G. Neko’s loop

可以先预处理，从i开始的为k的循环节，如果vis[j]=1的话一定在之前就算过了

计算时我们有两种考虑，一种是完整跳完循环后，最后多出的余数部分，跳最大值（因为开始点可以是循环中的任意部分，所以我们只需控制长度最大为m的最大和就可以了，这里可以用单调队列控制，并保证长度为m即可）

但由于mod部分可能就是全负数，所以我们可以退回一部分，跳完完整的之后，跳部分的len，这样我们可以得到max2部分，两者相比就是这一段的最大值；

而题中要求计算的是，最小的y使得，y+MAX>=s，相减即可！

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
//max（work(len)*(kk-1),work(mod)+sum(len)*m/len)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
int n,m,k,cnt;
ll s,MAX,v[maxn];
bool vis[maxn];
vector<ll>g[maxn];
ll q[maxn<<1],pre[maxn],st[maxn];
ll getsum(int x,ll y){
    ll len=g[x].size();
    for(int i=0;i<len;i++) q[i]=q[i+len]=g[x][i];
    len=len<<1;
    int l=0,r=0;
    ll ans=0;
    for(int i=0;i<len;i++){
        if(i==0) pre[i]=q[i];//前缀和
        else pre[i]=pre[i-1]+q[i];
        if(i<y){
            ans=max(ans,pre[i]);
        }
        while(l<len&&st[l]+y<i) l++;//控制长度
        if(l<r){
            ans=max(ans,pre[i]-pre[st[l]]);
        }
        
        while(l<r&&pre[i]<=pre[st[r-1]]) r--;//维护单调递减数列
        st[r++]=i;
    }
    return ans;
}
ll work(int x){
    ll len=g[x].size();
    ll mod=m%len;ll kk=m/len;
    ll sum=0;
    for(int i=0;i<len;i++) sum+=g[x][i];
    ll max1=getsum(x, mod)+max(0LL,sum)*kk;
    ll max2=getsum(x, len);
    if(kk>2){
        max2+=max(0LL,sum)*(kk-1);
    }
    return max(max1,max2);
    return max1;
}
void init(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++) g[i].clear();
    cnt=0;MAX=0;
}
int main(){
    int T;scanf("%d",&T);
    int kase=0;
    while(T--){
        scanf("%d%lld%d%d",&n,&s,&m,&k);
        init();
        for(int i=0;i<n;i++) scanf("%lld",&v[i]);
        for(int i=0;i<n;i++){//预处理从i开始跳的循环节
            if(!vis[i]){
                vis[i]=1;
                g[++cnt].push_back(v[i]);
                for(int j=(i+k)%n;!vis[j];j=(j+k)%n){
                    vis[j]=1;
                    g[cnt].push_back(v[j]);
                }
//                for(int j=0;j<g[cnt].size();j++)
//                    cout << g[cnt][j]<<" ";
//                cout <<endl;
                
                MAX=max(MAX,work(cnt));
//                cout<<"MAX "<<MAX<<endl;
            }
        }
        if(MAX>=s) printf("Case #%d: 0\n",++kase);
        else printf("Case #%d: %lld\n",++kase,s-MAX);
    }
    return 0;
}

H. Search for Answer(不会啊)

I. Tree and Permutation

全排列由n!，每一种排列里有n-1条边，除去顺序的问题，则每种边有$\frac {n!(n-1)}{C_n^2}=2(n-2)!$，对于每种边u-v(u\=v)。我们可以想象成一棵树，则v之后的子节点通过dfs可以知道，u上面的结点的个数就是n-dp[v]-1，于是通过u-v的条数有$dp[v]*(n-dp[v]-1)+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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAX = 1e5 + 5;
const ll mod = 1e9 + 7;
int head[MAX], cnt;
struct Edge {
    int to, nex, c;
}e[MAX<<1];
void add(int u, int v, int c) {
    e[++cnt].to = v;
    e[cnt].nex = head[u];
    e[cnt].c = c;
    head[u] = cnt;
}
ll sum;
int n, dp[MAX];
int dfs1(int u, int fa) {
    int v;
    for (int i = head[u]; i; i = e[i].nex) {
        v = e[i].to;
        if (v == fa)    continue;
        dp[u] += dfs1(v, u) + 1;
    }
    return dp[u];
}
void dfs2(int u, int fa) {
    int v;
    for (int i = head[u]; i; i = e[i].nex) {
        v = e[i].to;
        if (v == fa)    continue;
        sum += (1LL*(n - dp[v] - 1) * e[i].c * (dp[v] + 1))% mod;
        sum %= mod;
        dfs2(v, u);
        // cout << "here:" << sum  << ' ' << n << ' ' << dp[v] << ' ' << v << endl;
    }
}
ll fac[MAX];
void init() {
    memset(head, 0, sizeof(head));
    memset(dp, 0, sizeof(dp));
    cnt = 0;
    sum = 0;
}
int main() {
    fac[0] = 1;
    for (int i = 1; i < MAX; ++i) fac[i] = fac[i - 1] * i % mod;
    int u, v, c;
    while (scanf("%d", &n) != EOF) {
        init();
        for (int i = 1; i < n; ++i) {
            scanf("%d%d%d", &u, &v, &c);
            add(u, v, c);
            add(v, u, c);
        }
        dfs1(1, -1);
        dfs2(1, -1);
        ll ans = ((2 * fac[n-1] % mod) * sum % mod + mod) % mod;
        printf("%lld\n", ans);
    }
}

J. YJJ’s Salesman

当时在赛场上考虑，如何找到y和x同时小的那个点，后来看了题解发现，我们将y排完序后，之前的点除了同y的点，之前的点在x-1找最大值即可；那我们在更新dp的时候，可以将x从大到小排序，这样我们更新的时候不会影响同y的dp值了。

同时因为x,y的取值范围太大，所以我们需要进行离散化

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
const int MAX = 1e5 + 5;
set<int>XX;
set<int>::iterator it;
map<int,int>newnum;
int T, n,num;
int bit[MAX<<2], dp[MAX],dp2[MAX];
int lowbit(int k){
    return k&(-k);
}
void update(int pos,int num){
    while(pos<=n){
        bit[pos]=max(bit[pos],num);
        pos+=lowbit(pos);
    }
}
int query(int k){
    int anss=0;
    while(k>0){
        anss=max(anss,bit[k]);
        k-=lowbit(k);
    }
    return anss;
}
struct Point {
    int x, y, val;
    bool operator < (const Point b) const {
        if (y != b.y)   return y < b.y;
        return x > b.x;
    }
}p[MAX];
void init() {
    memset(bit, 0, sizeof(bit));
    memset(dp, 0, sizeof(dp));
    XX.clear();num=0;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        init();
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i){
            scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].val);
            XX.insert(p[i].x);
        }
        sort(p + 1, p + 1 + n);
        for(it=XX.begin();it!=XX.end();it++) {
            newnum[(*it)]=++num;
        }
        
        int ans = 0,a,b;
        for (int i = 1; i <= n; ++i) {
            a=newnum[p[i].x];
            b=query(a-1);
            dp[a]=max(b+p[i].val,dp[a]);
            update(a, dp[a]);
            ans=max(ans,dp[a]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

碎碎念

大清早，被一个混蛋搞的心情不好

把昨天场上遗留的题补了，发现，嗯……其实还好！差一点

也许是因为洛谷的签到太有毒了吧！

米歇尔·弗菲好美啊！如果我老了也那么好看就好啦！

偷得浮生半日闲，蚁人2的轻松小幽默还是很适合我的呢

虽然漏了一个彩蛋，不过刷知乎的时候，发现不亏！

睡了好久的我，昏昏沉沉，继续啪啪啪，敲代码吧！

突然觉得自己亏了，因为很可能这个混蛋，正在兴奋忘乎所以地继续钻研他毕生所爱

冷暴力战斗，战斗值100%！哼！

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽