第一周 8.29 - 9.4-白红宇

第一周 8.29 - 9.4

阅读量：5304 次

发布时间：2019-06-14

本文共 13966 字，大约阅读时间需要 46 分钟。

开学了>_<

8.29

Round B APAC Test 2017

昨天下午做了下 g 家的笔试..真的好菜啊..差好远..好好补下题叭

给出 n,A,B,k ，使得( i^A + j^B) % k == 0 的 i ，j 有多少对(i != j , 1 <= i <= n , 1 <= j <= n)

可以按照模 k 的余数分类

然后将两边的余数组合起来

cnt[x] * cnt[k-x] (0 <= x <= k-1)，再将 i = j 的统计出来减掉

好多地方都要取模..找好久错

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 typedef long long LL; 7 const LL mod = 1e9+7; 8 const int maxn = 1e6+5; 9 LL A,B,k,n;10 LL ca[maxn],cb[maxn],cc[maxn];11 LL cnt[maxn];12 13 LL qpow(LL a, LL b,LL MOD)14 {15     LL ret = 1LL;16     while(b)17     {18         if(b & 1) ret = ret * a % MOD;19         a = a * a % MOD;20         b >>= 1;21     }22     return ret;23 }24 25 void solve(){26     LL tot = n/k;27     LL yu = n%k;28     for(int i = 1;i <= k;i++){29         cnt[i%k] = tot;30         if(i <= yu) cnt[i%k]++;31         cnt[i%k] = (cnt[i%k]+mod) % mod;32     }33     for(int i = 1;i <= min(n,k);i++){34         int l = qpow(i,A,k) % k;35         int r = qpow(i,B,k) % k;36         ca[l] = (ca[l] + cnt[i%k]) % mod;37         cb[r] = (cb[r] + cnt[i%k]) % mod;38         if((l+r) % k == 0){39             cc[i%k] = (cc[i%k]+cnt[i%k]) % mod;40         }41     }42     43     /*for(int i = 0;i <= k;i++){44         printf("cnt[%d] = %I64d ca[%d] = %I64d cb[%d] = %I64d cc[%d] = %I64d\n",i,cnt[i],i,ca[i],i,cb[i],i,cc[i]);45     }*/46 47     LL ans = 0;48     for(int i = 0;i < k;i++){49         int l = i;l = l%k;50         int r = k-i;r = r%k;51         LL tmp = (ca[l]*cb[r])%mod;52         ans = (ans+tmp) % mod;53         ans = (ans-cc[i%k]+mod) % mod;54     }55     printf("%I64d\n",ans);56 }57 58 int main(){59     int T,kase = 0;60     freopen("B-large-practice.in","r",stdin);61     freopen("output.out","w",stdout);62     scanf("%d",&T);63     while(T--){64         scanf("%I64d %I64d %I64d %I64d",&A,&B,&n,&k);65         printf("Case #%d: ",++kase);66         memset(ca,0LL,sizeof(ca));67         memset(cb,0LL,sizeof(cb));68         memset(cc,0LL,sizeof(cc));69         memset(cnt,0LL,sizeof(cnt));70         solve();71     }72     return 0;73 }

View Code

8.30

给出 n 个区间，问任意删掉一个区间后，被覆盖的数的最少的个数

小数据:n <= 1000

大数据:n <= 100000

小数据直接 n2暴力，枚举每次删掉的区间，再O(n) 算一遍多少个数被覆盖

当时，O(n) 扫的时候写挫了..

维护一个 left 和 right

如果当前区间 a[i].l <= right 就扩大区间，也就是更新 right

如果当前区间 a[i].l > right ，就计算值

每次的rigth-left+1 相当于是在计算前一个区间，所以扫完 n 之后，还要再加上 right-left+1

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 typedef long long LL; 7  8 const int maxn = 1005; 9 const long long INF = (1LL << 50);10 LL l[maxn],r[maxn],x[maxn],y[maxn];11 12 LL n,L1,R1,A,B,C1,C2,m;13 14 struct node{15     LL l,r;16 }a[maxn];17 18 int cmp(node n1,node n2){19     if(n1.l != n2.l) return n1.l < n2.l;20     return n1.r < n2.r;21 }22 23 void solve(){24     LL ans = INF;25     sort(a+1,a+n+1,cmp);26   /*  for(int i = 1;i <= n;i++){27         printf("a[%d].l = %I64d r = %I64d\n",i,a[i].l,a[i].r);28     }*/29     for(int i = 1;i <= n;i++){30         LL tmp = 0LL;31         LL left = 0LL,right = -1LL;32         for(int j = 1;j <= n;j++){33             if(i == j) continue;34             if(a[j].l <= right){35                 right = max(right,a[j].r);36             }37             else{38                 tmp += right - left + 1LL;39                 left = a[j].l;40                 right = a[j].r;41             }42         }43         tmp += right - left+1;44         ans = min(ans,tmp);45     }46     printf("%I64d\n",ans);47 }48 49 int main(){50     int T,kase = 0;51     freopen("C-small-practice.in","r",stdin);52     freopen("out.out","w",stdout);53     scanf("%d",&T);54     while(T--){55         scanf("%I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d",&n,&L1,&R1,&A,&B,&C1,&C2,&m);56         x[1] = L1;y[1] = R1;57         a[1].l = L1;a[1].r = R1;58         for(int i = 2;i <= n;i++){59             x[i] = (A*x[i-1] + B*y[i-1] + C1) % m;60             y[i] = (A*y[i-1] + B*x[i-1] + C2) % m;61             a[i].l = min(x[i],y[i]);62             a[i].r = max(x[i],y[i]);63         }64         printf("Case #%d: ",++kase);65         solve();66     }67     return 0;68 }

View Code

补cf

c 的初始化写错一点..fst了..好桑心

但是 n4为啥不T呢...比赛的时候又想不到优化..鼓起勇气写暴力..sigh

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 typedef long long LL; 7 const int maxn = 1e5+5; 8 const long long INF = (1LL << 50); 9 10 int n,m,K,a[maxn];11 LL dp[105][105][105];12 LL p[105][105];13 14 void solve(){15     for(int i = 1;i <= n;i++){16         for(int j = 0;j <= K;j++){17             for(int k = 0;k <= m;k++) {18                 dp[i][j][k] = INF;19             }20         }21     }22     if(a[1] == 0){23         for(int i = 1;i <= m;i++) dp[1][1][i] = p[1][i];24     }25     else dp[1][1][a[1]] = 0;26     27     for(int i = 2;i <= n;i++){28         for(int j = 1;j <= min(i,K);j++){29             if(a[i] == 0){30                 for(int k = 1;k <= m;k++){31                     dp[i][j][k] = min(dp[i-1][j][k]+p[i][k],dp[i][j][k]);32                     //printf("=== dp[%d][%d][%d] = %I64d\n",i,j,k,dp[i][j][k]);33                     for(int z = 1;z <= m;z++){34                         if(z == k) continue;35                         dp[i][j][k] = min(dp[i][j][k],dp[i-1][j-1][z]+p[i][k]);36                     }37                     //printf("-----dp[%d][%d][%d] = %I64d\n",i,j,k,dp[i][j][k]);38                 }39             }40             else{41                 dp[i][j][a[i]] = min(dp[i][j][a[i]],dp[i-1][j][a[i]]);42                 for(int k = 1;k <= m;k++){43                     if(k == a[i]) continue;44                     dp[i][j][a[i]] = min(dp[i][j][a[i]],dp[i-1][j-1][k]);45                 }46             }47         }48     }49 50 /*    for(int i = 1;i <= n;i++){51         for(int j = 1;j <= K;j++){52             for(int k = 1;k <= m;k++)53                 printf("dp[%d][%d][%d] = %I64d\n",i,j,k,dp[i][j][k]);54         }55     }*/56 57     LL ans = INF;58     for(int i = 1;i <= m;i++) ans = min(ans,dp[n][K][i]);59     if(ans == INF) puts("-1");60     else printf("%I64d\n",ans);61 }62 63 int main(){64     while(scanf("%d %d %d",&n,&m,&K) != EOF){65         for(int i = 1;i <= n;i++) scanf("%d",&a[i]);66         for(int i = 1;i <= n;i++){67             for(int j = 1;j <= m;j++) scanf("%I64d",&p[i][j]);68         }69         solve();70     }71     return 0;72 }

View Code

找环..用的tarjan

看了一神的找环，太晦涩了...

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 typedef long long LL; 9 const long long mod = 1e9+7; 10 const int maxn = 1e6+5; 11 int n,m; 12 int first[maxn]; 13 int sc[maxn],scn[maxn],low[maxn],pre[maxn]; 14 int scnt,ecnt,dfs_clock; 15 int a[maxn]; 16 17 struct Edge{ 18 int v,next; 19 }e[maxn*10]; 20 21 stack
            
              S; 22 23 void init(){ 24 ecnt = 0; 25 memset(first,-1,sizeof(first)); 26 } 27 28 void addedges(int u,int v){ 29 e[ecnt].v = v; 30 e[ecnt].next = first[u]; 31 first[u] = ecnt++; 32 } 33 34 LL qpow(LL a, LL b) 35 { 36 LL ret = 1LL; 37 while(b) 38 { 39 if(b & 1) ret = ret * a % mod; 40 a = a * a % mod; 41 b >>= 1; 42 } 43 return ret; 44 } 45 46 void dfs(int u){ 47 low[u] = pre[u] = ++dfs_clock; 48 S.push(u); 49 for(int i = first[u];~i;i = e[i].next){ 50 int v = e[i].v; 51 if(!pre[v]){ 52 dfs(v); 53 low[u] = min(low[u],low[v]); 54 } 55 else if(!sc[v]) low[u] = min(low[u],pre[v]); 56 } 57 if(pre[u] == low[u]){ 58 scnt++; 59 for(;;){ 60 int x = S.top();S.pop(); 61 sc[x] = scnt; 62 scn[scnt]++; 63 if(x == u) break; 64 } 65 } 66 } 67 68 void find_scc(){ 69 while(!S.empty()) S.pop(); 70 scnt = dfs_clock = 0; 71 memset(low,0,sizeof(low));memset(pre,0,sizeof(pre)); 72 memset(sc,0,sizeof(sc));memset(scn,0,sizeof(scn)); 73 74 for(int i = 1;i <= n;i++) if(!pre[i]) dfs(i); 75 } 76 77 void solve(){ 78 find_scc(); 79 LL ans = 1LL; 80 // printf("scnt = %d\n",scnt); 81 //for(int i = 1;i <= n;i++) printf("sc[%d] = %d\n",i,sc[i]); 82 LL tot = 0LL; 83 for(int i = 1;i <= scnt;i++){ 84 if(scn[i] == 1) tot++; 85 else{ 86 LL tmp = (qpow(2,scn[i]) -2LL+mod) % mod; 87 ans = (ans*tmp) % mod; 88 } 89 } 90 LL tmp = qpow(2,tot)%mod; 91 ans = (ans*tmp) % mod; 92 printf("%I64d\n",ans); 93 } 94 95 int main(){ 96 while(scanf("%d",&n) != EOF){ 97 init(); 98 for(int i = 1;i <= n;i++) { 99 scanf("%d",&a[i]);100 addedges(i,a[i]);101 }102 solve();103 }104 return 0;105 }

View Code

8.31

公式很好想

(2^n)*(2^n-1)*....*(2^n-k+1) / (2^n)^k

本来...人家给的2^n 就算一个特殊一点的地方..

然后我跑去令 N = 2^n

化简成 N*(N-1)*...(N-k+1)/N^k

更加看不出来该怎么做了...wwwwwww

先把分子有多少个 2 提取出来

然后因为模数很小，根据抽屉原理

在min(mod,k) 里面肯定能过算出分子

--------------------------------------------------

还有一个地方就是 2^n 要先约掉

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 typedef long long LL; 7 const long long mod = 1e6+3; 8  9 LL n,k;10 11 LL gcd(LL a,LL b){12     return (!b) ? a : gcd(b,a%b);13 }14 15 LL qpow(LL a, LL b){16     LL ret = 1LL;17     while(b){18         if(b & 1) ret = ret * a % mod;19         a = a * a % mod;20         b >>= 1;21     }22     return ret;23 }24 25 LL inv(LL x){26     return qpow(x, mod - 2);27 }28 29 void solve(){30     if(n <= 60 && k > (1LL << n)){31         puts("1 1");32         return;33     }34     LL cnt = 0LL;35     LL y = k-1;36     while(y){37         cnt += y/2LL;38         y = y/2LL;39     }40     //printf("cnt = %I64d\n",cnt);41     LL fz = 1LL,fm = 1LL;42     fm = qpow(2LL,n);43     //printf("fm = %I64d\n",fm);44     for(int i = 2;i <= k;i++){45         LL tmp = (fm-i+1+mod) % mod;46         fz = (fz * tmp) % mod;47         //printf("i = %d fz = %I64d fm-i-1 = %I64d\n",i,fz,fm-i-1);48         if(fz == 0) break;49     }50     LL chu = qpow(2LL,cnt);51     fz = (fz*inv(chu)) % mod;52     fm = qpow(fm,k-1) % mod;53     fm = (fm*inv(chu)) % mod;54     fz = (fm-fz+mod) % mod;55     //printf("fz = %I64d fm = %I64d\n",fz,fm);56     //LL g = gcd(fz,fm);57     //fz = fz/g;fm = fm/g;58     printf("%I64d %I64d\n",fz,fm);59 }60 61 int main(){62     while(scanf("%I64d %I64d",&n,&k) != EOF){63         solve();64     }65     return 0;66 }

View Code

9.1

新的一个月！！！>_<

又好久没做几何了

在 cf 上点开几何的标签开始做...

cf 261 B

给出操作后的正方体的 8 个顶点，有个人可能把每个顶点的坐标进行过交换，他还可以对每个顶点这样

问能不能还原成一个正方体

暴力枚举所有的情况

判断正方体，可以用距离来判断

是 x 的点有 3个

是sqrt2 x 的点3个

是 sqrt3 x 的点有 1个

不想写..

cf 660 d

给出 n 个点，问能够组成多少个平行四边形

去年冬天的题了，当时司老大还教了我，现在又忘记了

n2 枚举点对，统计它们的中点被经过的次数

然后每一个中点 Cn 2 大概是一个中点对应一条对角线，从中任意选两条出来的意思

9.2

什么都没干

这道题想不通有 3 个的时候怎么画的

9.3

很久以前看 q 神在 Acdream群里说，cf 上的哪道几何题我没做过..orzorz

cf 14 c

给出 4 条线段，问能否形成一个长方形

写的姿势不对，wa了好多次

后来用题解的写法

先保存不同的点的个数，有解的情况一定是 4个

再算出 xmin ymin xmax ymax （这点没想到）

确定出四个端点的坐标，确定出四条边，再看这4条边在原本给出的边里是否存在

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7  8 struct node{ 9     int x1,y1,x2,y2;10 }line[15];11 12 set
           
            
              > s;13 set
             
              
               
                ,pair
                
                  > > h;14 15 void solve(){16 if(s.size() != 4){17 puts("NO");18 return;19 }20 int xmin,xmax,ymin,ymax;21 xmin = xmax = line[1].x1;22 ymin = ymax = line[1].y1;23 for(set
                 
                  
                    >::iterator it = s.begin();it != s.end();++it){24 pair
                   
                     tmp = *it;25 xmin = min(tmp.first,xmin);26 xmax = max(tmp.first,xmax);27 ymin = min(tmp.second,ymin);28 ymax = max(tmp.second,ymax);29 }30 if(xmin == xmax || ymin == ymax){31 puts("NO");32 return;33 }34 int cnt = 0;35 pair
                    
                      A = make_pair(xmin,ymin);36 pair
                     
                       B = make_pair(xmin,ymax);37 pair
                      
                        C = make_pair(xmax,ymax);38 pair
                       
                         D = make_pair(xmax,ymin);39 if(h.find(make_pair(A,B)) != h.end()|| h.find(make_pair(B,A)) != h.end()) cnt++;40 if(h.find(make_pair(B,C)) != h.end() || h.find(make_pair(C,B))!= h.end()) cnt++;41 if(h.find(make_pair(C,D)) != h.end()|| h.find(make_pair(D,C))!= h.end()) cnt++;42 if(h.find(make_pair(D,A)) != h.end()|| h.find(make_pair(A,D))!= h.end()) cnt++;43 if(cnt == 4) puts("YES");44 else puts("NO");45 }46 47 int main(){48 for(int i = 1;i <= 4;i++){49 scanf("%d %d %d %d",&line[i].x1,&line[i].y1,&line[i].x2,&line[i].y2);50 pair
                        
                          u = make_pair(line[i].x1,line[i].y1);51 pair
                         
                           v = make_pair(line[i].x2,line[i].y2);52 s.insert(u);53 s.insert(v);54 h.insert(make_pair(u,v));55 }56 solve();57 return 0;58 }

View Code

接着做一道几何...实在不会..

原来是斜率优化的dp....滚去学一下下

9.4

cf 319 c

有 n 棵树，不用按照顺序砍，每棵树的高度是 a[i] ，每个充电器的费用是 b[j]

每砍一棵树的花费是 a[i]*b[j](b[j] 是已经被砍成0的树的b的最小值)

当编号为 n 的树被砍掉之后，其余的树再被砍就不需要花钱了

问所有的树砍光的最小花费

dp[n] = min(dp[j] + b[j]*a[i])

然后看的这篇

把条件改一改，就是一样的了

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 typedef long long LL; 7 const int maxn = 1e5+5; 8 LL dp[maxn],a[maxn],b[maxn]; 9 int q[maxn];10 11 int n;12 13 int check(int k,int j,int i){14     double l = (1.0*(dp[k]-dp[j])) / (1.0*(b[j]-b[k]));15     double r = (1.0*(dp[j]-dp[i])) / (1.0*(b[i]-b[j]));16     return l >= r;17 }18 19 void solve(){20     dp[1] = 0LL;21     int L = 1,R = 2;22     q[1] = 1;23     for(int i = 2;i <= n;i++){24         while(L+1 < R && (dp[q[L+1]]-dp[q[L]]) < (b[q[L]]*a[i]-b[q[L+1]]*a[i])) ++L;25         int j = q[L];26         dp[i] = dp[j] + b[j]*a[i];27         while(L+1 < R && R > 2 && check(q[R-2],q[R-1],i)) --R;28         q[R++] = i;29         //printf("dp[%d] = %I64d L = %d R = %d\n",i,dp[i],L,R);30     }31     printf("%I64d\n",dp[n]);32 }33 34 int main(){35     while(scanf("%d",&n) != EOF){36         for(int i = 1;i <= n;i++) scanf("%I64d",&a[i]);37         for(int i = 1;i <= n;i++) scanf("%I64d",&b[i]);38         solve();39     }    40     return 0;41 }