抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

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

Tabris

CSDN套题待补

发布于：2017年7月16日

次浏览

[原创]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) ，然后妥妥的 TLE 了，

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

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

最后复杂度为O(Tqnm/a) ，其中a为 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^2
f(i)为以a(i)结尾的 lis 的长度

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

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

过程中只要记录 长度为l的上升序列当前的最小结尾是谁 ，然后每次看长度为f[i]-1的序列的结尾和a[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)=ax^2+bxy+cy^2，问你是否永远非负

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

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

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

G 2017

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

考虑到 2017 是素数，满足的情况用坐标系表示的话一定在x,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 的方阵 求每个子矩阵的元素和的三次方的和

未完待续...

\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)\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(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)$的 代码没写 [看dalao的吧](https://www.icpc-camp.org/submissions/4rtbv6xCtpW8Hd) # K 2017 Revenge ———————————————————————————————————————————————— 对于**原根**理解的十分不到位,只停留到会计算,,,, 算是强行补题. 大概了解下[原根](https://zh.wikipedia.org/wiki/%E5%8E%9F%E6%A0%B9)在了解些什么是[生成元](https://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E6%A8%A1n%E4%B9%98%E6%B3%95%E7%BE%A4)这题就可以做了 将乘法转化为加法 ~~个人理解其实这部分相当去将a*x%2017和a*y%2017的结果进行了优化,能够方便记录每一位的值~~ 考虑dp[i][j] 表示到第i个点后取模结果为j的数的个数 然后优化下空间到dp[2017]; 每次转移就是$dp[i][j*x]+=dp[i-1][j],dp[i][j*x]%=2,j\in[0,2016]$ 然后因为转化为加法后 能够快速找到值, 又有最后的结果要对$2$取模 能够想到二进制的方法做, 这里采用了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=\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}

问你$\displaystyle \sum_{i\leq i <j<k<l\le n}a_ia_ja_ka_l$ ----- 有了s3 , 所以可以先求3个数的情况,然后找第4个数, 然后发现,每次如果第4个数选择$a[x]$,那么结果就多了$a[x]\times \displaystyle \sum_{i\leq i <j<k< x}a_ia_ja_k$ 所以遍历一遍序列,即固定$a[l]$ 同时能求出$\displaystyle \sum_{i=1}^n a_i \sum_{i=1}^n a_i^2 \sum_{i=1}^n a_i^3$ 从而能$O(1)$求出$\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;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://blog.tabris.top/acm/2017-07-16-75208683/

本页文档最后更新于：2021年5月16日

CSDN

评论