C. C. Blog

Security Research, Algorithm and Data Structure

发表于 更新于 分类于 ，
本文字数： 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...

发表于 更新于 分类于 ，
本文字数： 1.4k 阅读时长 ≈ 2 分钟

Problem

In Chinese mythology, Pangu is the first living being and the creator of the sky and the earth. He woke up from an egg and split the egg into two parts: the sky and the earth.

At the beginning, there was no mountain on the earth, only stones all over the land.

There were N piles of stones, numbered from 1 to N. Pangu wanted to merge all of them into one pile to build a great mountain. If the sum of stones of some piles was S, Pangu would need S seconds to pile them into one pile, and there would be S stones in the new pile.

Unfortunately, every time Pangu could only merge successive piles into one pile. And the number of piles he merged shouldn't be less than L or greater than R.

Pangu wanted to finish this as soon as possible.

Can you help him? If there was no solution, you should answer '0'.

Input

There are multiple test cases.

The first line of each case contains three integers N,L,R as above mentioned (2<=N<=100,2<=L<=R<=N).

The second line of each case contains N integers a1,a2 …aN (1<= ai <=1000,i= 1…N ), indicating the number of stones of pile 1, pile 2 …pile N.

The number of test cases is less than 110 and there are at most 5 test cases in which N >= 50.

Output

For each test case, you should output the minimum time(in seconds) Pangu had to take . If it was impossible for Pangu to do his job, you should output 0.

阅读全文 »

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

在阅读这篇文章之前，我们假定你已经掌握了KMP:n+1次探里的定义。

引入：扩展KMP是干什么的

扩展KMP解决的是源串S的每一个后缀与模式串P的最长公共前缀的长度的问题，并求解出答案extend数组，例如，ababac与aba的extend数组是3 0 3 0 1 0，这里extend[i]表示s[i:5]（i从0开始）与p[0:2]的最长公共前缀的长度。

next数组的定义

这里的next数组与KMP里的不同。

next[i]表示从i开始的p的后缀与p的最长公共前缀的长度，也就是，p对p求扩展KMP，可以参见2019 Multi-University Training Contest 5 - 1006 - string matching。

我们先假设已经有了next数组，来求extend，因为next数组的求法是和extend一样的。

扩展KMP

递推：已知extend[i-1]，如何求extend[i]？

我们假设在前面匹配时，向右匹配到的最远坐标为last，是从first开始匹配的，也就是说s[first:last]=p[0:last-first]。可以推出s[i:last]=p[i-first:last-first]，但这个不是和p的开头匹配，还不能用，我们取extend[i]=min(last-i+1, next[i-first])，看看p[i-first:last-first]和p开头有多少相同。然后向后检测extend[i]能不能更大，这一块暴力，别忘了最后更新first和last。

初始：暴力大法好

暴力检测s和p最大公共前缀长度extend[0]。

求next数组

和上面一样。next的0位置必定是p的长度，代码中last初值设为0是为了避免初始化。

例题

阅读全文 »

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

\[y = x^2\]

可以创建行内公式，例如 \(\Gamma(n) = (n-1)!\quad\forall n\in\mathbb N\)。或者块级公式：

\[ x = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2a} \]

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

学自【谈谈知识点】快速幂&龟速乘&快速乘 - Cyan_rose的博客 - CSDN博客

基础快速幂

直接上代码

1
2
3
4
5
6
7
8
9
ll speed(ll a,ll b,ll p){
    ll cur=a,ans=1;
    while(b){
        if(b&1) ans=ans*cur%p;
        cur=cur*cur%p;
        b>>=1;
    }
    return ans%p;
}

龟速乘

乘法换成加法，原理差不多就是把其中一个乘数二进制拆分，每次让另一个乘数翻倍，能乘的时候就乘，因为只是翻倍，所以不会超范围。

c++ ll lowspeed(ll a,ll b,ll p){ ll cur=a,ans=0; while(b){ if(b&1) ans=(ans+cur)%p; cur=(cur+cur)%p; b>>=1; } return ans%p; } ll speed(ll a,ll b,ll p){ ll cur=a,ans=1; while(b){ if(b&1) ans=lowspeed(ans,cur,p)%p; cur=lowspeed(cur,cur,p)%p; b>>=1; } return ans%p; }

发表于 更新于 分类于 ，
本文字数： 571 阅读时长 ≈ 1 分钟
  1. n mod 2^k = n&((1<<k)-1)
  2. 判断n是否为2的正整数幂n>1 && !(n&(n-1))

位压缩：

  1. 读取第k位：a>>k&1
  2. 读取第k位并取反：~a>>k&1
  3. 将第k位清0：a&=~(1<<k)
  4. 将第k位置1：a|=1<<k
  5. 将第k位取反：a^=1<<k
  6. 将第k1~k2位反转：a^=((1<<(k2-k1+1))-1)<<k2 （？）
  7. 是否恰好只有一个true：!(x&(x-1))&&x
  8. 判断是否有两个相邻的true：x>>1&x
  9. 是否有三个相邻的true：x>>1&x>>2&x

打包位统计：

  1. 统计true的个数的奇偶性：x=x>>1;x=x>>2;x=x>>4;x=x>>8;x^=x>>16; 之后：(x>>k1^x>>(k2+1))&1
  2. 统计true的个数1：每次n&=n-1，计数器+1
  3. 统计true的个数2： 
    1
    2
    3
    4
    5
    6
    7
    8
    int count(unsigned int x){//注意传入uint
        x=(x&0x55555555)+(x>>1&0x55555555);
        x=(x&0x33333333)+(x>>2&0x33333333);
        x=(x&0x0F0F0F0F)+(x>>4&0x0F0F0F0F);
        x=(x&0x00FF00FF)+(x>>8&0x00FF00FF);
        x=(x&0x0000FFFF)+(x>>16&0x0000FFFF);
        return x;
    }
  4. 反转位的顺序： 
    1
    2
    3
    4
    5
    6
    7
    8
    unsigned int rev(unsigned int x){
        x=(x&0x55555555)<<1|(x>>1&0x55555555);
        x=(x&0x33333333)<<2|(x>>2&0x33333333);
        x=(x&0x0F0F0F0F)<<4|(x>>4&0x0F0F0F0F);
        x=(x&0x00FF00FF)<<8|(x>>8&0x00FF00FF);
        x=(x&0x0000FFFF)<<16|(x>>16&0x0000FFFF);
        return x;
    }

消除分支：

  1. 计算绝对值： 

    1
    2
    3
    4
    int abs(int x){
        int y=x>>31;
        return (x+y)^y;
    }

  2. 求最大值： 

    1
    2
    3
    4
    int max(int x,int y){
        int m=(x-y)>>31;
        return y&m|x&~m;
    }

其他：

  1. 交换变量： 
    1
    2
    3
    void swap(int& x,int& y){x^=y;y^=x;x^=y;};
    //C++可以写成x^=y^=x^=y
    //Java不行

感谢骆神犇，09年的文再看还是大有收获。

发表于 更新于 分类于 ，
本文字数： 2.2k 阅读时长 ≈ 4 分钟

ZOJ2002

题目

Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.

Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered 1, 2 ... m) that may have different number of pages (p1, p2 ... pm) and you want to make one copy of each of them. Your task is to divide these books among k scribes, k <= m. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 0 = b0 < b1 < b2, ... < bk-1 <= bk = m such that i-th scriber gets a sequence of books with numbers between bi-1+1 and bi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.

阅读全文 »

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

题目

N * N的方格，从左上到右下画一条线。一个机器人从左上走到右下，只能向右或向下走。并要求只能在这条线的上面或下面走，不能穿越这条线，有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10007的结果。 N<=1e9

思路

卡特兰数+卢卡斯定理+乘法逆元算组合数

卡特兰数：某百科卡特兰数词条讲过这种情况。

卢卡斯定理：组合数，模数很小，逐次拆分

乘法逆元，见前面，此处n+1不能保证和p互质，建议用卡特兰数两组合数相减的公式。（不过数据很弱我写的/(n+1)）

阅读全文 »