首页 > 代码库 > 寒假训练4解题报告
寒假训练4解题报告
1. Cosmic Tables
数据量比较大，这里不能直接暴力，用行指针和列指针表示当前行列是原来的第几行第几列
#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int N = 1005;int n ,m , k , row[N] , col[N] , a[N][N];char s[5] ;int p1 , p2;int main(){ // freopen("a.in" , "r" , stdin); while(scanf("%d%d%d" , &n , &m , &k) == 3) { for(int i=1 ; i<=n ; i++) for(int j =1 ; j<=m ; j++) scanf("%d" , &a[i][j]); int maxn = max(n , m); for(int i=1; i<=maxn ; i++) row[i] = i , col[i] = i; for(int i=1 ; i<=k ; i++){ scanf("%s%d%d" , s , &p1 , &p2); if(s[0] == ‘g‘) printf("%d\n" , a[row[p1]][col[p2]]); else if(s[0] == ‘c‘){ int t = col[p1]; col[p1] = col[p2] , col[p2] = t; } else{ int t = row[p1]; row[p1] = row[p2] , row[p2] = t; } } } return 0;}
2. Reducing Fractions
先打表记录10^7内的所有素因子
题目比较简单，但过程写的有点长，记录a数组中总共包含了多少的素因子，并记录其个数
然后根据这个个数不断将b[]中的元素消去以最大可能消去这些因子，但不超过a[]中所记录的因子数，并记录消去的因子数，说明这些数目的因子在a[]中也存在这么多
然后再返回将a[]中的元素也消去这么多因子
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cmath> 5 using namespace std; 6 const int N = 100005; 7 const int maxn = 10000000; 8 int a[N] , b[N]; 9 bool vis[maxn]; 10 int prime[maxn/10] , k , cnt[maxn/10] , del[maxn/10]; 11 12 void get_prime() 13 { 14 k=0; 15 memset(vis , 0 , sizeof(vis)); 16 for(int i=2 ; i<maxn ; i++){ 17 if(!vis[i]){ 18 prime[k++] = i; 19 for(int j=i+i ; j<maxn ; j+=i) vis[j] = true; 20 } 21 } 22 } 23 24 int bin_seach(int x) 25 { 26 int l=0 , r = k-1; 27 while(l<=r){ 28 int m = (l+r)>>1; 29 if(prime[m] == x) return m; 30 else if(prime[m] > x) r = m-1; 31 else l=m+1; 32 } 33 } 34 35 void get_factor(int x) 36 { 37 int t = (int)sqrt(x+0.5); 38 for(int i=0 ; i<k ; i++){ 39 if(prime[i]*prime[i] > x) break; 40 if(x % prime[i] == 0){ 41 while(x % prime[i] == 0) 42 { 43 x /= prime[i]; 44 cnt[i]++; 45 } 46 } 47 } 48 if(x>1) cnt[bin_seach(x)]++; 49 } 50 51 int del_factor(int x) 52 { 53 int m = x; 54 int t = (int)sqrt(x+0.5); 55 for(int i=0 ; i<k ; i++){ 56 if(prime[i]*prime[i] > x) break; 57 if(x % prime[i] == 0){ 58 while(x % prime[i] == 0) 59 { 60 if(cnt[i]) m/=prime[i] , cnt[i]--,del[i]++; 61 x /= prime[i]; 62 } 63 } 64 } 65 if(x>1){ 66 int pos = bin_seach(x); 67 if(cnt[pos]) m/=prime[pos] , cnt[pos]--,del[pos]++; 68 } 69 return m; 70 } 71 72 int get_a(int x) 73 { 74 int m = x; 75 int t = (int)sqrt(x+0.5); 76 for(int i=0 ; i<k ; i++){ 77 if(prime[i]*prime[i] > x) break; 78 if(x % prime[i] == 0){ 79 while(x % prime[i] == 0) 80 { 81 if(del[i]) m/=prime[i] ,del[i]--; 82 x /= prime[i]; 83 } 84 } 85 } 86 if(x>1){ 87 int pos = bin_seach(x); 88 if(del[pos]) m/=prime[pos] , del[pos]--; 89 } 90 return m; 91 } 92 93 int main() 94 { 95 // freopen("a.in" , "r" , stdin); 96 get_prime(); 97 int n,m; 98 while(scanf("%d%d" , &n , &m) == 2) 99 {100 memset(cnt , 0 , sizeof(cnt));101 for(int i=0 ; i<n ; i++)102 {103 scanf("%d" , a+i);104 get_factor(a[i]);105 }106 memset(del , 0 , sizeof(del));107 for(int i=0 ; i<m ; i++)108 {109 scanf("%d" , b+i);110 int tmp = b[i];111 b[i] = del_factor(tmp);112 }113 114 for(int i=0 ; i<n ; i++)115 {116 int tmp = a[i];117 a[i] = get_a(tmp);118 }119 printf("%d %d\n" , n , m);120 for(int i=0 ; i<n ; i++){121 if(i == 0) printf("%d" , a[i]);122 else printf(" %d" , a[i]);123 }124 puts("");125 for(int i=0 ; i<m ; i++){126 if(i == 0) printf("%d" , b[i]);127 else printf(" %d" , b[i]);128 }129 puts("");130 }131 return 0;132 }
3. Olympiad
一道简单的贪心，最好情况必然为第一名，最差情况，可以先排序，a[] 由小到大, b[]由大到小，每次取尽可能多的成立的组，然后让其作为所有组的最后一名即可
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>using namespace std;const int N = 100005;int a[N] , b[N] , sum[N] , vis[N];bool cmp(int a , int b){ return a>b;}int main(){ // freopen("a.in" , "r" , stdin); int n , k; while(scanf("%d%d" , &n , &k) == 2) { for(int i=0 ; i<n ; i++) scanf("%d", a+i); sort(a , a+n); for(int i=0 ; i<n ; i++) scanf("%d", b+i); sort(b , b+n , cmp); memset(vis , 0 , sizeof(vis)); int ans=0 , flag = 0; int index = 0 ; for(int i=0 ; i<n ; i++) { while(b[i]+a[index]<k || vis[index]){ if(index == n-1){flag = 1 ;break;} index = (index+1)%n; } if(flag) break; vis[index]=1; ans++; index = (index+1)%n; } printf("%d %d\n" , 1 , ans); } return 0;}
4. Good Substrings
用字典树记录已存在的字符串，但不要傻傻的添加字符串时都从root开始，因为我们都是从某一点出发，每次往后多添加一个字符，所以第一层循环中可以每次都保留当前访问到的字典树的位置，从这个位置向下一格就好，否则会超时
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>using namespace std;const int N = 1600;char s1[N] , s2[N];int sum[N] , k;bool good[N];struct Node{ Node *next[26]; int flag; Node(){ flag = 0; for(int i=0 ; i<26 ; i++) next[i] = NULL; }};Node *root;Node *cur;void add_string(int i , int &ans){ int id = s1[i]-‘a‘; if(cur->next[id] == NULL) cur->next[id] = new Node(); cur = cur->next[id]; if(cur->flag == 0) ans++; cur->flag = 1;}int main(){ // freopen("a.in" , "r" , stdin); int k; while(scanf("%s" , s1+1) == 1) { scanf("%s%d" , s2 , &k); for(int i=0 ; i<26 ; i++) good[i] = s2[i] == ‘1‘; int len = strlen(s1+1); for(int i=1 ; i<=len ; i++){ sum[i] = sum[i-1]; if(!good[s1[i]-‘a‘]) sum[i]++; } root = new Node(); int ans = 0; for(int l=1 ; l<=len ; l++){ cur = root; for(int r=l ; r<=len ; r++){ if(sum[r] - sum[l-1] <= k) add_string(r,ans); } } printf("%d\n" , ans); } return 0;}
5. Decoding Genome
一道dp题目，开始想到了要dp，不过一看n的取值就放弃dp了，不得不说自己很傻
当n值很大总应想到logn解决问题的矩阵快速幂
dp[i][c] 表示前 i 个字符，以 字符c结尾的种数 ， 这里 c 有 m 种，所以用 m*m的矩阵进行快速幂即可
#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define ll long longconst int N = 1<<6;const int MOD = 1000000007;int dp[30],m,k;ll n;char s[4];struct Matrix{ ll mat[52][52]; Matrix operator*(const Matrix &p)const{ Matrix ans; for(int i=0 ; i<m ; i++){ for(int j=0 ; j<m ; j++){ ans.mat[i][j] = 0; for(int k=0 ; k<m ; k++){ ans.mat[i][j] += mat[i][k]*p.mat[k][j]; ans.mat[i][j] %= MOD; } } } return ans; } void print() { for(int i=0 ; i<m ; i++){ for(int j=0 ; j<m ; j++) cout<<mat[i][j]<<" "; cout<<endl; } }};Matrix qpow(ll cnt , Matrix p){ Matrix ans; for(int i=0 ; i<m ; i++) for(int j=0 ; j<m ; j++) if(i == j) ans.mat[i][j] = 1; else ans.mat[i][j] = 0; while(cnt){ if(cnt&1) ans = ans*p; p = p*p; cnt/=2; } return ans;}int char_to_int(char c){ if(c>=‘a‘&&c<=‘z‘) return c-‘a‘; else return 26+(int)(c-‘A‘);}int main(){ // freopen("a.in" , "r" , stdin); while(scanf("%I64d%d%d" , &n , &m , &k) == 3) { Matrix p ; for(int i=0 ; i<m ; i++) for(int j=0 ; j<m ; j++) p.mat[i][j] = 1; for(int i=0;i<m;i++) dp[i]=1; for(int i=0 ; i<k ; i++) { scanf("%s" , s); int g = char_to_int(s[0]); int h = char_to_int(s[1]); p.mat[g][h] = 0; } Matrix final = qpow(n-1 , p); ll ans = 0; for(int i=0 ; i<m ; i++) for(int j=0 ; j<m ; j++){ ans += dp[i]*final.mat[j][i]; ans %= MOD; } printf("%I64d\n" , ans); } return 0;}
寒假训练4解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。