C. C. Blog

Security Research, Algorithm and Data Structure

ICPC2019银川网 络 赛

发表于 更新于 分类于 ，
本文字数： 869 阅读时长 ≈ 1 分钟

真实菜鸡，被AK打蒙了，签到都最后才找到的。

A.Maximum Element In A Stack

Problem

栈操作，每次操作后求最大值。

Solution

加入时加此时堆里的最大值，要开long long。

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
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x7fffffffffffffff
#define mem(a, x) memset(a,x,sizeof(a))
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
ll power(ll a, ll b,ll p) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % p; a = a * a % p; } return res; }
ll gcd(ll p, ll q) { return q == 0 ? p : gcd(q, p % q); }
ll _abs(ll x){return x < 0 ? -x : x;}
using namespace std;
const int mod = 1e9 + 7;
const int N = 5e6+10;

int n,p,q,m;
unsigned int SA,SB,SC;
ll a[N];

stack<unsigned int> s;
unsigned int rng61(){
    SA ^= SA<<16;
    SA ^= SA>>5;
    SA ^= SA<<1;
    unsigned int t = SA;SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}
inline void PUSH(unsigned int x){
    if(s.empty()) s.push(x);
    else s.push(max(x,s.top()));
}
inline void POP(){
    if(!s.empty()) s.pop();
}
void gen(){
    scanf("%d%d%d%d%u%u%u",&n,&p,&q,&m,&SA,&SB,&SC);
    for(int i=1;i<=n;i++){
        if(rng61() % (p+q) < p)
            PUSH(rng61() % m + 1);
        else
            POP();
        if(s.empty()) a[i]=0;
        else a[i]=s.top();
        a[i]*=i;
    }
}
int main(){
    int T;cin >> T;
    for(int i=1;i<=T;i++){
        while(!s.empty()) s.pop();
        gen();
        ll ans=a[1];
        for(int j=2;j<=n;j++)
            ans^=a[j];
        printf("Case #%d: %lld\n",i,ans);
    }
    return 0;
}

B.Rolling The Polygon

一开始看计算几何就没做，最后半小时发现很简单，298分钟过的...

Problem

给一个凸多边形和其内一点，求凸多边形在地下转一周，点走过的距离。

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
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x7fffffffffffffff
#define mem(a, x) memset(a,x,sizeof(a))
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
ll power(ll a, ll b,ll p) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % p; a = a * a % p; } return res; }
ll gcd(ll p, ll q) { return q == 0 ? p : gcd(q, p % q); }
ll _abs(ll x){return x < 0 ? -x : x;}
using namespace std;
int T,n;
int cnt=0,sx,sy;
struct E{
    int x,y;
}e[60];

double anss;
double l(int x1,int y1,int x2,int y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+0.0);
}
int main(){
    //cout<<acos(-1/sqrt(2.0));
    //io_opt;
    scanf("%d",&T);
    while(T--){
        anss=0;
        cnt++;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&e[i].x,&e[i].y);
        }
        scanf("%d%d",&sx,&sy);
        for(int i=1;i<=n;i++){
            int x1,x2,y1,y2;
            double tmp1=l(sx,sy,e[i].x,e[i].y);
            if(i==1){
                x1=e[n].x-e[1].x,y1=e[n].y-e[1].y;
                x2=e[2].x-e[1].x,y2=e[2].y-e[1].y;
            }
            else if(i==n){
                x1=e[n-1].x-e[n].x,y1=e[n-1].y-e[n].y;
                x2=e[1].x-e[n].x,y2=e[1].y-e[n].y;
            }
            else{
                x1=e[i-1].x-e[i].x,y1=e[i-1].y-e[i].y;
                x2=e[i+1].x-e[i].x,y2=e[i+1].y-e[i].y;
            }

            //cout<<'*'<<y1<<'*'<<endl;
            double tmp2=acos(-1)-(acos((x1*x2+y1*y2)*1.0/l(x1,y1,0,0)/l(x2,y2,0,0)));
            anss+=tmp1*tmp2;
            //cout<<i<<':'<<tmp1<<' '<<tmp2<<endl;
        }
        printf("Case #%d: %.3f\n",cnt,anss);
    }
    return 0;
}

C.Caesar Cipher

Problem

字母后移，给出示范和目标串，求原串。

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
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x7fffffffffffffff
#define mem(a, x) memset(a,x,sizeof(a))
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
ll power(ll a, ll b,ll p) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % p; a = a * a % p; } return res; }
ll gcd(ll p, ll q) { return q == 0 ? p : gcd(q, p % q); }
ll _abs(ll x){return x < 0 ? -x : x;}
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5+10;
int n,m;
char a[N],b[N],c[N],ans[N];
int main(){
    int T;scanf("%d",&T);
    for(int i=1;i<=T;i++){
        scanf("%d%d",&n,&m);
        scanf("%s%s%s",a,b,c);
        int d=b[0]-a[0];
        int j=0;
        for(j=0;j<m;j++){
            int ss=c[j]-d;
            while(ss<'A') ss+=26;
            while(ss>'Z') ss-=26;
            ans[j]=ss;
        }
        ans[j]='\0';
        printf("Case #%d: %s\n",i,ans);
    }
    return 0;
}

D.Take Your Seat

Problems

n个乘客分别属于n个座位，顺序坐，第一个随机坐，后面的如果被占了就随机，否则坐自己的，求最后一个坐自己位置的概率。 m同样，不过乘客坐座位顺序随机。

Solution

n=1显然为1，n=2显然为1/2，n=3的时候，P(3)=1/3*(1+P(2)+0)，n=4，P(4)=1/4*(1+P(3)+P(2)+0)。

以4为例解释，1号坐在每个位置概率为1/4，当他坐在自己位置，4号必然坐到自己位置，概率为1；1号坐在2号，相当于2号随机坐（疯了），2号的原位置可以视作1，整个删除1号和他坐的2号位置，问题变为P(3)；1号坐在3号位置，2号坐对了，他也删去，规模变为P(2)；1号坐在4号，概率为0。

所以推测不是1的时候概率都是1/2，可以直接敲了（或者数学归纳法证明）。

m=1时也是1，1号最后登机时坐在自己位置概率为1，否则可以视作他前面的都正常删去，转化为第一个问题，则m不是1时，P(m)=1/m*(1+1/2*(m-1))。

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
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x7fffffffffffffff
#define mem(a, x) memset(a,x,sizeof(a))
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
ll power(ll a, ll b,ll p) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % p; a = a * a % p; } return res; }
ll gcd(ll p, ll q) { return q == 0 ? p : gcd(q, p % q); }
ll _abs(ll x){return x < 0 ? -x : x;}
using namespace std;
int T,n,m;
int cnt=0,sx,sy;
struct E{
    int x,y;
}e[60];

double anss;
double l(int x1,int y1,int x2,int y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+0.0);
}
int main(){
    //cout<<acos(-1/sqrt(2.0));
    //io_opt;
    scanf("%d",&T);
    while(T--){
        cnt++;
        scanf("%d%d",&n,&m);
        double ans1=(n==1?1.0:0.5),ans2=(m==1?1:(m+1)/2.0/m);
        printf("Case #%d: %.6f %6f\n",cnt,ans1,ans2);
    }
    return 0;
}

H.Fight Against Monsters

Problem

回合制，勇士打n个怪，每个有hp和atk（血量和攻击），勇士打每一个怪的伤害分别计算，第一次是1，第二次是2，每次加1，怪物先手，问勇士受到的最小伤害。

Solution

hp转成击败次数，贪心，除法排序。

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
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x7fffffffffffffff
#define mem(a, x) memset(a,x,sizeof(a))
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
ll power(ll a, ll b,ll p) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % p; a = a * a % p; } return res; }
ll gcd(ll p, ll q) { return q == 0 ? p : gcd(q, p % q); }
ll _abs(ll x){return x < 0 ? -x : x;}
using namespace std;
int T,n;
struct E{
    int hp,atk;
    ll sum;
}e[100020];
int cmp(E x,E y){
    if(x.atk*y.hp==y.atk*x.hp) return x.atk<y.atk;
    return x.atk*y.hp<y.atk*x.hp;
}
bool check(int x,int s){
    return x>=s;
}
int ef(int s){
    int l=1,r=1e3,mid,ans;
    while(l<=r){
        mid=(l+r)>>1;
        if(check((mid+1)*mid/2,s)){
            r=mid-1;
            ans=mid;
        }
        else{
            l=mid+1;
        }
    }
    return ans;
}
int cnt=0;
int main(){
    io_opt;
    cin>>T;
    while(T--){
        cnt++;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>e[i].hp>>e[i].atk;
            e[i].hp=ef(e[i].hp);
        }
        sort(e+1,e+1+n,cmp);
        for(int i=1;i<=n;i++){
            if(i==1){
                e[i].sum=e[i].atk;
            }
            else{
                e[i].sum=e[i-1].sum+e[i].atk;
            }
        }
        ll ans=0,tmp;
        for(int i=n;i>=1;i--){
            //cout<<e[i].hp<<endl;
            tmp=e[i].hp;
            tmp*=e[i].sum;
            ans+=tmp;
        }
        cout<<"Case #"<<cnt<<": "<<ans<<endl;
    }
    return 0;
}

Continue...

  • 本文作者： CCWUCMCTS
  • 本文链接： https://ccwucmcts.github.io/posts/53295/
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

欢迎关注