[原创]2017年四川省赛 【(5+2+1)/12】 [待补]

2017-07-16 18:15:11 Tabris_ 阅读数：934

博客爬取于2020-06-14 22:39:39
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/75208683

链接： https://post.icpc-camp.org/d/691-2017

A Simple Arithmetic

————————————————————————————————————————————————

签到题
注意-2^63 的情况和2^63不能用64位长度的数表示就好了

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 <bits/stdc++.h>

typedef long long int LL;
using namespace std;

const int N = 200000+7;

inline int read() {
    int x=0,f=1;
    char ch=getchar();
    for(; ch<'0'||'9'<ch; ch=getchar())   if(ch=='-')f=-1;
    for(; '0'<=ch&&ch<='9'; ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}

/*******************************************************/

int main() {
    long double a,b;
    while(cin>>a>>b) {
        if(a == -9223372036854775808.0) {
//            puts("++");
            if(a == b) {
                puts("1");
            } else if(b==-1.0) {
                puts("9223372036854775808");
            } else if(b==1.0) {
                puts("-9223372036854775808");
            } else {
                LL ans = floor(a/b);
                printf("%lld\n",ans);
            }
            continue;
        } else if(b == -9223372036854775808.0) {
            if(a<0) puts("-1");
            else    puts("0");
            continue;
        }
        if(a<0&&b<0) a*=-1.0,b*=-1.0;
//        cout << (LL)a <<" "<<  (LL)b <<endl;
        LL ans = floor(a/b);
        printf("%lld\n",ans);
    }
    return 0;
}

B Broken Counter

————————————————————————————————————————————————

C Determinant

————————————————————————————————————————————————

D Dynamic Graph

————————————————————————————————————————————————
给你一个DAG图,每个节点不是白的就是黑的,有q次操作,每次将点x变换颜色.然后输出当前< u,v>有多少对,
< u,v>定义为; 当存在一条从u到v的路径使得路径上没有黑色的点是存在.

考虑到DAG图，所以进行拓扑排序，
每次操作完，之后将黑色的点去掉，然后进行拓扑序，在过程中记录能到达每个点的个数，然后一路算过去就行了，然后去个重复采用vis标记,复杂度是O(Tqnm)O(Tqnm) ,然后妥妥的TLE了,

最后想到用二进制来优化,每一位对应表示每一个节点,然后进行TOP过程中与一下就行了.

可以用5个64位整形计算 (这时候注意求1的个数的时候要用lowbit优化)
也可以用bitset来计算

最后复杂度为O(Tqnm/a)O(Tqnm/a) ,其中aa为bitset优化的常数

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

typedef long long int LL;
using namespace std;

const int N = 1100+7;
const int MOD = 1e9+7;
inline LL read() {
    LL x=0,f=1;
    char ch=getchar();
    for(; ch<'0'||'9'<ch; ch=getchar())   if(ch=='-')f=-1;
    for(; '0'<=ch&&ch<='9'; ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}

/*******************************************************/

int n,m,q,ans;

vector<int>G[303];
int vis[303],c[303],deg[303],temp[303];

void TOP() {
    bitset<303>mmp[303];
    ans = 0;
    queue<int>q;
    for(int i=1; i<=n; i++) {
        if(deg[i]==0) {
            q.push(i);
        }
        temp[i]=deg[i];
    }
    for(int i=1; i<=n; i++) {
        mmp[i][i]=1;
    }
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=0; i<G[u].size(); i++) {
            int v=G[u][i];
            if(c[v]==0&&c[u]==0) {
                mmp[v]=mmp[v]|mmp[u];
            }
            temp[v]--;
            if(temp[v]==0)q.push(v);
        }
    }
    for(int i=1; i<=n; i++) {
        if(c[i]==0)
            ans+=mmp[i].count()-1;
        //   printf("%d ---%d\n",c[i],mmp[i].count()-1);
    }
    printf("%d\n",ans);
}

int main() {
    while(~scanf("%d%d%d",&n,&m,&q)) {
        memset(c,0,sizeof(c));
        memset(deg,0,sizeof(deg));
        for(int i=1; i<=n; i++)G[i].clear();
        for(int i=1,u,v; i<=m; i++) {
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            deg[v]++;
        }
        for(int x; q--;) {
            scanf("%d",&x);
            c[x]=1-c[x];
            TOP();
        }
    }
    return 0;
}

E Longest Increasing Subsequence

————————————————————————————————————————————————
给你个序列 问你去除每个数之后剩下的数中的结果
结果定义为 $\displaystyle f_1^2 \xor f_2^2 \xor … \xor f_n^2f(i)为以为以a(i)$结尾的lis的长度

最暴力的想法是求nn遍lislis复杂度为O(n2log⁡n)O(n^2\log n) ,一定TLE， 然后想如何优化为O(n2)O(n^2)

然后想到删除一个数之后对f(i)f(i)的影响至多减少1, 所以在我们有了原序列的f(i)f(i)之后 我们就可以O(2n)O(2n)的求每次新的f(i)f(i)

过程中只要记录 长度为ll的上升序列当前的最小结尾是谁 ,然后每次看长度为f[i]−1f[i]-1的序列的结尾和a[i]a[i]比谁大 就能判断f(i)f(i)是否减了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
# include <bits/stdc++.h>

typedef long long int LL;
using namespace std;

const int N = 5000+7;
const int MOD = 1e9+7;
const int INF = (~(1<<31));

inline LL read() {
    LL x=0,f=1;
    char ch=getchar();
    for(; ch<'0'||'9'<ch; ch=getchar())   if(ch=='-')f=-1;
    for(; '0'<=ch&&ch<='9'; ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}

/*******************************************************/
int n;

int a[N],b[N],f[N];

int main() {
    while(~scanf("%d",&n)) {
        for(int i=1; i<=n; i++) scanf("%d",&a[i]);

        for(int i=1; i<=n; i++) {
            f[i]=1;
            for(int j=1; j<i; j++) if(a[i]>a[j])
                    f[i]=max(f[i],f[j]+1);
        }

        int ans,tmp;
        for(int k=1; k<=n; k++) {
            for(int i=1; i<=n; i++) b[i] = INF;
            ans = 0;
            for(int i=1; i<=n; i++) {
                if(i==k) continue;

                if(b[f[i]-1] < a[i]) tmp = f[i];
                else                 tmp = f[i]-1;

                ans   ^= (tmp*tmp);
                b[tmp] = min(b[tmp],a[i]);
            }

            printf("%d%c",ans,(k==n)?'\n':' ');
        }
    }
    return 0;
}

F Simple Algebra

————————————————————————————————————————————————
给你f(x,y)=ax2+bxy+cy2f(x,y)=ax^2+bxy+cy^2,问你是否永远非负

考虑到数据范围只有[−10,10][-10,10]，于是选择打表，

判断过程是计算x,y∈[−1000,1000]x,y\in[-1000,1000] 过程中有没有负的,然后输出{0,1}\{0,1\}

代码太长了 http://paste.ubuntu.com/25102699/

G 2017

————————————————————————————————————————————————
给你4个数a,b,c,d .       0≤a≤b≤109,0≤c≤d≤109a,b,c,d\ . \ \ \ \ \ \ \ 0\le a \le b \le 10^9 , 0\le c \le d \le10^9
问你∑i=ab∑j=cd[i∗j%2017=0]\displaystyle \sum_{i=a}^b \sum_{j=c}^d \Big[i*j\%2017 = 0\Big]

考虑到2017是素数，满足的情况用坐标系表示的话一定在x,y=2017kx,y = 2017k上 ,所以直接计算就好了

1
2
3
4
5
6
7
8
9
10
11
LL cal(LL a,LL b){
    LL ans = (a/2017)*b+(b/2017)*a-(a/2017)*(b/2017);
    return ans;
}

int main(){
    LL a,b,c,d;
    while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d))
        printf("%lld\n",cal(b,d)-cal(b,c-1)-cal(a-1,d)+cal(a-1,c-1));
    return 0;
}

H Roads

————————————————————————————————————————————————

I Strange Prime

————————————————————————————————————————————————

J Skewness

————————————————————————————————————————————————

给你一个n*n的方阵 求每个子矩阵的元素和的三次方的和

未完待续…

∑x1=1n∑y1=1n∑x2=x1n∑y2=y1n(∑i=x1x2∑j=y1y2ai,j)3mod  109∑x1=1n∑y1=1n∑x2=x1n∑y2=y1n(f(x2,y2)−f(x2,y1−1)−f(x1−1,y2)+f(x1−1,y1−1))3mod  109\sum_{x_1=1}^n\sum_{y_1=1}^n\sum_{x_2=x_1}^n\sum_{y_2=y_1}^n \Big(\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2} a_{i,j}\Big)^3 \mod 10^9\\ \sum_{x_1=1}^n\sum_{y_1=1}^n\sum_{x_2=x_1}^n\sum_{y_2=y_1}^n \Big(f(x2,y2)-f(x2,y1-1)-f(x1-1,y2)+f(x1-1,y1-1))^3 \mod 10^9

其中

(f(x2,y2)−f(x2,y1−1)−f(x1−1,y2)+f(x1−1,y1−1))3=(a−b−c+d)3=(a−b−c+d)×(a−b−c+d)×(a−b−c+d)=(a−b−c+d)×(a2+b2+c2+d2−2ab−2ac+2ad+2bc−2bd−2cd)=(a3−b3−c3+d3+6(bcd−acd−abd+abc)+3(ab2−a2b−a2c+ac2+a2d+ad2−b2c−bc2+b2d−bd2+c2d−cd2))(f(x2,y2)-f(x2,y1-1)-f(x1-1,y2)+f(x1-1,y1-1))^3 \\ = (a-b-c+d)^3 \\ = (a-b-c+d)\times(a-b-c+d)\times(a-b-c+d) \\ = (a-b-c+d)\times(a^2 + b^2 + c^2+d^2 -2ab-2ac+2ad+2bc-2bd-2cd) \\ = (a^3-b^3-c^3+d^3+6(bcd-acd-abd+abc)\\+3(ab^2-a^2b -a^2c +ac^2 +a^2d +ad^2 -b^2c -bc^2 +b^2d - bd^2 +c^2d -cd^2))

其中

a(a2+b2+c2+d2−2ab−2ac+2ad+2bc−2bd−2cd)=a3+ab2+ac2+ad2−2a2b−2a2c+2a2d+2abc−2abd−2acd −b(a2+b2+c2+d2−2ab−2ac+2ad+2bc−2bd−2cd)=−a2b−b3−bc2−bd2+2ab2+2abc−2abd−2b2c+2b2d+2bcd −c(a2+b2+c2+d2−2ab−2ac+2ad+2bc−2bd−2cd)=−a2c−b2c−c3−cd2+2abc+2ac2−2acd−2bc2+2bcd+2c2d d(a2+b2+c2+d2−2ab−2ac+2ad+2bc−2bd−2cd)=a2d+b2d+c2d+d3−2abd−2acd+2ad2+2bcd−2bd2−2cd2a(a^2 + b^2 + c^2+d^2 -2ab-2ac+2ad+2bc-2bd-2cd) \\= a^3 + ab^2 + ac^2+ad^2 -2a^2b-2a^2c+2a^2d+2abc-2abd-2acd \\ \ \\ -b(a^2 + b^2 + c^2+d^2 -2ab-2ac+2ad+2bc-2bd-2cd) \\ = -a^2b - b^3 - bc^2-bd^2 +2ab^2+2abc-2abd-2b^2c+2b^2d+2bcd \\ \ \\ -c(a^2 + b^2 + c^2+d^2 -2ab-2ac+2ad+2bc-2bd-2cd)\\= -a^2c - b^2c - c^3-cd^2 +2abc+2ac^2-2acd-2bc^2+2bcd+2c^2d \\ \ \\ d(a^2 + b^2 + c^2+d^2 -2ab-2ac+2ad+2bc-2bd-2cd)\\= a^2d + b^2d + c^2d+d^3 -2abd-2acd+2ad^2+2bcd-2bd^2-2cd^2

我TM是有多无聊 会来补这个题，，，MD 不补了

然后在对于每种情况的求一下对结果的贡献系数

然后推到一下 ，就需要在预处理出几种前缀和，后缀和，

然后统计即可 总复杂度是O(n)O(n)的

代码没写 看dalao的吧

K 2017 Revenge

————————————————————————————————————————————————

对于原根理解的十分不到位,只停留到会计算,

算是强行补题.

大概了解下原根在了解些什么是生成元这题就可以做了

将乘法转化为加法

个人理解其实这部分相当去将ax%2017和ay%2017的结果进行了优化,能够方便记录每一位的值

考虑dp[i][j] 表示到第i个点后取模结果为j的数的个数 然后优化下空间到dp[2017];

每次转移就是dp[i][j∗x]+=dp[i−1][j],dp[i][j∗x]dp[i][j*x]+=dp[i-1][j],dp[i][j*x]%=2,j\in[0,2016]

然后因为转化为加法后 能够快速找到值, 又有最后的结果要对22取模 能够想到二进制的方法做,

这里采用了bitset

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

int p[N];
int n,r;
int get(int mod) {
    for(int i = 2; ; i++) {
        set<int> s;
        for(int j = 1, x = 1; j < mod; j++) {
            x = (x*i)%mod;
            s.insert(x);
        }
        if(s.size() == mod-1) return i;
    }
}

int main() {
    // cout << get(2017) << endl;
    // 5 为模 2017 的 原根
    for(int i = 0, x = 1; i < 2016; i++) {
        p[x] = i;
        x = (x*5)%2017;
    }
    while(~scanf("%d%d", &n, &r)) {
        bitset<2016> f;
        f[p[1]] = 1;
        for(int i = 0; i < n; i++) {
            int x; scanf("%d", &x); x = p[x];
            f ^= (f<<x) ^ (f>>(2016-x));
        }
        printf("%d\n", (int)f[p[r]]);
    }
    return 0;
}

L Nice Trick

————————————————————————————————————————————————
给你一个序列以及

s3=∑i≤i<j<k≤naiajak=(∑i=1nai)3−3(∑i=1nai2)(∑i=1nai)+2(∑i=1nai3)6s3=\sum_{i\leq i <j<k\le n}a_ia_ja_k = \\ \dfrac{(\sum_{i=1}^n a_i)^3-3(\sum_{i=1}^n a_i^2)(\sum_{i=1}^n a_i)+2(\sum_{i=1}^n a_i^3)}{6}

问你∑i≤i<j<k<l≤naiajakal\displaystyle \sum_{i\leq i <j<k<l\le n}a_ia_ja_ka_l

有了s3 , 所以可以先求3个数的情况,然后找第4个数,

然后发现,每次如果第4个数选择a[x]a[x],那么结果就多了a[x]×∑i≤i<j<k<xaiajaka[x]\times \displaystyle \sum_{i\leq i <j<k< x}a_ia_ja_k

所以遍历一遍序列,即固定a[l]a[l] 同时能求出∑i=1nai∑i=1nai2∑i=1nai3\displaystyle \sum_{i=1}^n a_i \sum_{i=1}^n a_i^2 \sum_{i=1}^n a_i^3 从而能O(1)O(1)求出∑i≤i<j<k<laiajak\displaystyle \sum_{i\leq i <j<k< l}a_ia_ja_k

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

typedef long long int LL;
using namespace std;

const int N = 200000+7;
const int MOD = 1e9+7;

inline int read() {
    int x=0,f=1;
    char ch=getchar();
    for(; ch<'0'||'9'<ch; ch=getchar())   if(ch=='-')f=-1;
    for(; '0'<=ch&&ch<='9'; ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}

/*******************************************************/

LL qmod(LL a,LL b){
    LL res = 1ll;
    while(b){
        if(b&1) res=res*a%MOD;
        b>>=1,a=a*a%MOD;
    }
    return res;
}
int n ;

LL inv6 = qmod(6,MOD-2);
LL a[N];
LL cal(LL a1,LL a2,LL a3){
    LL ans = 0;
    ans += qmod(a1,3);
    ans -= a1*a2%MOD*3%MOD; ans = (ans % MOD + MOD ) %MOD;
    ans += a3*2%MOD; ans %= MOD;
    return ans*inv6%MOD;
}
int main(){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

        LL a1 = 0,a2 = 0,a3 = 0,ans = 0,tmp = 0;
        for(int i=1;i<=n;i++){
            if(i>3){
                tmp  = a[i]*cal(a1,a2,a3)%MOD;
                ans += tmp;
                ans %= MOD;
            }
            a1+=a[i];
            a2+=a[i]*a[i]%MOD;
            a3+=qmod(a[i],3);
            a1%=MOD,a2%=MOD,a3%=MOD;
//            printf(" %lld --->> %lld \n",tmp,ans);
        }
        printf("%lld\n",ans%MOD);
    }
    return 0;
}