[原创]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 ( T q n m ) O(Tqnm) O ( Tq nm ) ,然后妥妥的TLE了,
最后想到用二进制来优化,每一位对应表示每一个节点,然后进行TOP过程中与 一下就行了.
可以用5个64位整形计算 (这时候注意求1的个数的时候要用lowbit优化) 也可以用bitset来计算
最后复杂度为O ( T q n m / a ) O(Tqnm/a) O ( Tq nm / a ) ,其中a 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 n n 遍l i s lis l i s 复杂度为O ( n 2 log n ) O(n^2\log n) O ( n 2 log n ) ,一定TLE, 然后想如何优化为O ( n 2 ) O(n^2) O ( n 2 )
然后想到删除一个数之后对f ( i ) f(i) f ( i ) 的影响至多减少1, 所以在我们有了原序列的f ( i ) f(i) f ( i ) 之后 我们就可以O ( 2 n ) O(2n) O ( 2 n ) 的求每次新的f ( i ) f(i) f ( i )
过程中只要记录 长度为l l l 的上升序列当前的最小结尾是谁 ,然后每次看长度为f [ i ] − 1 f[i]-1 f [ i ] − 1 的序列的结尾和a [ i ] a[i] a [ i ] 比谁大 就能判断f ( 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 ) = a x 2 + b x y + c y 2 f(x,y)=ax^2+bxy+cy^2 f ( x , y ) = a x 2 + b x y + c y 2 ,问你是否永远非负
考虑到数据范围只有[ − 10 , 10 ] [-10,10] [ − 10 , 10 ] ,于是选择打表,
判断过程是计算x , y ∈ [ − 1000 , 1000 ] x,y\in[-1000,1000] x , y ∈ [ − 1000 , 1000 ] 过程中有没有负的,然后输出{ 0 , 1 } \{0,1\} { 0 , 1 }
代码太长了 http://paste.ubuntu.com/25102699/
G 2017 ———————————————————————————————————————————————— 给你4个数a , b , c , d . 0 ≤ a ≤ b ≤ 1 0 9 , 0 ≤ c ≤ d ≤ 1 0 9 a,b,c,d\ . \ \ \ \ \ \ \ 0\le a \le b \le 10^9 , 0\le c \le d \le10^9 a , b , c , d . 0 ≤ a ≤ b ≤ 1 0 9 , 0 ≤ c ≤ d ≤ 1 0 9 问你∑ i = a b ∑ j = c d [ i ∗ j % 2017 = 0 ] \displaystyle \sum_{i=a}^b \sum_{j=c}^d \Big[i*j\%2017 = 0\Big] i = a ∑ b j = c ∑ d [ i ∗ j %2017 = 0 ]
考虑到2017是素数,满足的情况用坐标系表示的话一定在x , y = 2017 k x,y = 2017k x , y = 2017 k 上 ,所以直接计算就好了
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的方阵 求每个子矩阵的元素和的三次方的和
未完待续… ∑ x 1 = 1 n ∑ y 1 = 1 n ∑ x 2 = x 1 n ∑ y 2 = y 1 n ( ∑ i = x 1 x 2 ∑ j = y 1 y 2 a i , j ) 3 m o d 1 0 9 ∑ x 1 = 1 n ∑ y 1 = 1 n ∑ x 2 = x 1 n ∑ y 2 = y 1 n ( f ( x 2 , y 2 ) − f ( x 2 , y 1 − 1 ) − f ( x 1 − 1 , y 2 ) + f ( x 1 − 1 , y 1 − 1 ) ) 3 m o d 1 0 9 \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 x 1 = 1 ∑ n y 1 = 1 ∑ n x 2 = x 1 ∑ n y 2 = y 1 ∑ n ( i = x 1 ∑ x 2 j = y 1 ∑ y 2 a i , j ) 3 mod 1 0 9 x 1 = 1 ∑ n y 1 = 1 ∑ n x 2 = x 1 ∑ n y 2 = y 1 ∑ n ( f ( x 2 , y 2 ) − f ( x 2 , y 1 − 1 ) − f ( x 1 − 1 , y 2 ) + f ( x 1 − 1 , y 1 − 1 ) ) 3 mod 1 0 9
其中
( f ( x 2 , y 2 ) − f ( x 2 , y 1 − 1 ) − f ( x 1 − 1 , y 2 ) + f ( x 1 − 1 , y 1 − 1 ) ) 3 = ( a − b − c + d ) 3 = ( a − b − c + d ) × ( a − b − c + d ) × ( a − b − c + d ) = ( a − b − c + d ) × ( a 2 + b 2 + c 2 + d 2 − 2 a b − 2 a c + 2 a d + 2 b c − 2 b d − 2 c d ) = ( a 3 − b 3 − c 3 + d 3 + 6 ( b c d − a c d − a b d + a b c ) + 3 ( a b 2 − a 2 b − a 2 c + a c 2 + a 2 d + a d 2 − b 2 c − b c 2 + b 2 d − b d 2 + c 2 d − c d 2 ) ) (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)) ( f ( x 2 , y 2 ) − f ( x 2 , y 1 − 1 ) − f ( x 1 − 1 , y 2 ) + f ( x 1 − 1 , y 1 − 1 ) ) 3 = ( a − b − c + d ) 3 = ( a − b − c + d ) × ( a − b − c + d ) × ( a − b − c + d ) = ( a − b − c + d ) × ( a 2 + b 2 + c 2 + d 2 − 2 ab − 2 a c + 2 a d + 2 b c − 2 b d − 2 c d ) = ( a 3 − b 3 − c 3 + d 3 + 6 ( b c d − a c d − ab d + ab c ) + 3 ( a b 2 − a 2 b − a 2 c + a c 2 + a 2 d + a d 2 − b 2 c − b c 2 + b 2 d − b d 2 + c 2 d − c d 2 ))
其中
a ( a 2 + b 2 + c 2 + d 2 − 2 a b − 2 a c + 2 a d + 2 b c − 2 b d − 2 c d ) = a 3 + a b 2 + a c 2 + a d 2 − 2 a 2 b − 2 a 2 c + 2 a 2 d + 2 a b c − 2 a b d − 2 a c d − b ( a 2 + b 2 + c 2 + d 2 − 2 a b − 2 a c + 2 a d + 2 b c − 2 b d − 2 c d ) = − a 2 b − b 3 − b c 2 − b d 2 + 2 a b 2 + 2 a b c − 2 a b d − 2 b 2 c + 2 b 2 d + 2 b c d − c ( a 2 + b 2 + c 2 + d 2 − 2 a b − 2 a c + 2 a d + 2 b c − 2 b d − 2 c d ) = − a 2 c − b 2 c − c 3 − c d 2 + 2 a b c + 2 a c 2 − 2 a c d − 2 b c 2 + 2 b c d + 2 c 2 d d ( a 2 + b 2 + c 2 + d 2 − 2 a b − 2 a c + 2 a d + 2 b c − 2 b d − 2 c d ) = a 2 d + b 2 d + c 2 d + d 3 − 2 a b d − 2 a c d + 2 a d 2 + 2 b c d − 2 b d 2 − 2 c d 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 a ( a 2 + b 2 + c 2 + d 2 − 2 ab − 2 a c + 2 a d + 2 b c − 2 b d − 2 c d ) = a 3 + a b 2 + a c 2 + a d 2 − 2 a 2 b − 2 a 2 c + 2 a 2 d + 2 ab c − 2 ab d − 2 a c d − b ( a 2 + b 2 + c 2 + d 2 − 2 ab − 2 a c + 2 a d + 2 b c − 2 b d − 2 c d ) = − a 2 b − b 3 − b c 2 − b d 2 + 2 a b 2 + 2 ab c − 2 ab d − 2 b 2 c + 2 b 2 d + 2 b c d − c ( a 2 + b 2 + c 2 + d 2 − 2 ab − 2 a c + 2 a d + 2 b c − 2 b d − 2 c d ) = − a 2 c − b 2 c − c 3 − c d 2 + 2 ab c + 2 a c 2 − 2 a c d − 2 b c 2 + 2 b c d + 2 c 2 d d ( a 2 + b 2 + c 2 + d 2 − 2 ab − 2 a c + 2 a d + 2 b c − 2 b d − 2 c d ) = a 2 d + b 2 d + c 2 d + d 3 − 2 ab d − 2 a c d + 2 a d 2 + 2 b c d − 2 b d 2 − 2 c d 2
我TM是有多无聊 会来补这个题,,,MD 不补了
然后在对于每种情况的求一下对结果的贡献系数
然后推到一下 ,就需要在预处理出几种前缀和,后缀和,
然后统计即可 总复杂度是O ( n ) O(n) O ( n ) 的
代码没写 看dalao的吧
K 2017 Revenge ————————————————————————————————————————————————
对于原根 理解的十分不到位,只停留到会计算,
算是强行补题.
大概了解下原根 在了解些什么是生成元 这题就可以做了
将乘法转化为加法
个人理解其实这部分相当去将ax%2017和a y%2017的结果进行了优化,能够方便记录每一位的值
考虑dp[i][j] 表示到第i个点后取模结果为j的数的个数 然后优化下空间到dp[2017];
每次转移就是d p [ i ] [ j ∗ x ] + = d p [ i − 1 ] [ j ] , d p [ i ] [ j ∗ x ] dp[i][j*x]+=dp[i-1][j],dp[i][j*x]%=2,j\in[0,2016] d p [ i ] [ j ∗ x ] + = d p [ i − 1 ] [ j ] , d p [ i ] [ j ∗ x ]
然后因为转化为加法后 能够快速找到值, 又有最后的结果要对2 2 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 ———————————————————————————————————————————————— 给你一个序列以及
s 3 = ∑ i ≤ i < j < k ≤ n a i a j a k = ( ∑ i = 1 n a i ) 3 − 3 ( ∑ i = 1 n a i 2 ) ( ∑ i = 1 n a i ) + 2 ( ∑ i = 1 n a i 3 ) 6 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} s 3 = i ≤ i < j < k ≤ n ∑ a i a j a k = 6 ( ∑ i = 1 n a i ) 3 − 3 ( ∑ i = 1 n a i 2 ) ( ∑ i = 1 n a i ) + 2 ( ∑ i = 1 n a i 3 )
问你∑ i ≤ i < j < k < l ≤ n a i a j a k a l \displaystyle \sum_{i\leq i <j<k<l\le n}a_ia_ja_ka_l i ≤ i < j < k < l ≤ n ∑ a i a j a k a l
有了s3 , 所以可以先求3个数的情况,然后找第4个数,
然后发现,每次如果第4个数选择a [ x ] a[x] a [ x ] ,那么结果就多了a [ x ] × ∑ i ≤ i < j < k < x a i a j a k a[x]\times \displaystyle \sum_{i\leq i <j<k< x}a_ia_ja_k a [ x ] × i ≤ i < j < k < x ∑ a i a j a k
所以遍历一遍序列,即固定a [ l ] a[l] a [ l ] 同时能求出∑ i = 1 n a i ∑ i = 1 n a i 2 ∑ i = 1 n a i 3 \displaystyle \sum_{i=1}^n a_i \sum_{i=1}^n a_i^2 \sum_{i=1}^n a_i^3 i = 1 ∑ n a i i = 1 ∑ n a i 2 i = 1 ∑ n a i 3 从而能O ( 1 ) O(1) O ( 1 ) 求出∑ i ≤ i < j < k < l a i a j a k \displaystyle \sum_{i\leq i <j<k< l}a_ia_ja_k i ≤ i < j < k < l ∑ a i a j a 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; }