首页 > 代码库 > 寒假训练2解题报告
寒假训练2解题报告
1.CodeForces 112C
找一种可能满足其所给条件，为了让平方和尽可能大，那么我们总和总是取最大为y，分这个y时，尽可能少分这样得到的平方和才最大，所以其他元素都只分到1，留下一个最大元素，这里注意如果每个都分1不够分，直接表示无答案
#include <iostream>#include <cstring>#include <cstdio>using namespace std;#define ll long longconst int N = 100005;int a[N];int main(){ // freopen("a.in" , "r" , stdin); int n , y; ll x ; while(scanf("%d%I64d%d" , &n , &x , &y) == 3) { if(y < n){ puts("-1"); continue; } ll ans = 0; for(int i=1 ; i<=n ; i++) a[i]=1; a[1] = y-n+1; ans = (ll)a[1]*a[1] + (ll)(n-1); if(ans >= x){ for(int i=1 ; i<=n ; i++) printf("%d\n" , a[i]); } else puts("-1"); } return 0;}
2.CodeForces 112D
输出当前数的因子在其所给的前k个数中不存在的个数，我们用一个数组记录每一个因子上一次出现的位置，然后根据这个位置判断是不是在给定范围内出现
#include <iostream>#include <cstring>#include <cstdio>#include <vector>#include <cmath>using namespace std;const int N = 100005;int ans[N];int vis[N];//记录最近被访问的时候int main(){ // freopen("a.in" , "r" , stdin); int n,x,y; while(scanf("%d" , &n ) == 1) { memset(vis , 0 , sizeof(vis)); memset(ans , 0 , sizeof(ans)); for(int i=1 ; i<=n ; i++){ scanf("%d%d" , &x , &y); int t = (int)sqrt(x+0.5); // cout<<"t: "<<t<<endl; for(int j=1 ; j<=t ; j++){ if(x % j == 0){ if(vis[j]<i-y) ans[i]++; vis[j] = i; int p = x/j; if(p != j && vis[p]<i-y) ans[i]++; vis[p] = i; } } printf("%d\n" , ans[i]); } } return 0;}
3.CodeForces 112E
一道状态压缩p问题，这里可以理解为 一个 十字的图形可覆盖的加入到n*m中，问最少要多少个这样的十字图形
然后我们用1表示放置十字图形的中心，0表示没有放置十字图形的中心，每一行放十字图形的状态都只跟前两行有关，所以用dp[i][v][u]不断按行转移就好了
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = (1<<6);const int INF = 0x3f3f3f3f;int dp[45][N][N];void dfs(int i , int w , int v , int u , int k , int val){ if(k<0){ dp[i][v][u] = min(dp[i][v][u] , val); return ; } if(k>0 && !(v&(7<<(k-1))) && !(w&(1<<k))) dfs(i , w , v , u|(1<<k) , k-1 , val+1); else if(k==0 && !(v&(3<<(k))) && !(w&(1<<k))) dfs(i , w , v , u|(1<<k) , k-1 , val+1); else{ dfs(i , w , v , u|(1<<k) , k-1 , val+1); dfs(i,w,v,u,k-1,val); }}bool ok(int u,int v,int k){ for(int i=k ; i>=1 ; i--){ if(!(v&(1<<i)) && !(u&(7<<(i-1)))) return false; } if(!(v&1) && !(u&3)) return false; return true;}int main(){ // freopen("a.in" , "r" , stdin); int n,m; while(scanf("%d%d" , &n , &m) == 2) { if(n<m) swap(n,m); if(n==1){ int ans ; if(m%3 == 0) ans = m-m/3; else ans = m-1-m/3; printf("%d\n" , ans); continue; } memset(dp , 0x3f , sizeof(dp)); dp[0][(1<<m)-1][0]=0; for(int i=1 ; i<=n ; i++){ for(int w=0 ; w<(1<<m) ; w++){ for(int v=0 ; v<(1<<m) ; v++){ if(dp[i-1][w][v]<INF) dfs(i,w,v,0,m-1,dp[i-1][w][v]); } } } int ans = INF; for(int v=0 ; v<(1<<m) ; v++){ for(int u=0 ; u<(1<<m) ; u++){ if(dp[n][v][u]<INF && ok(u,v,m-1)){ ans = min(ans , dp[n][v][u]); } } } printf("%d\n" , n*m-ans); } return 0;}
4.CodeForces 159E
离散化所有颜色，一个塔搭建可以是由 两个都为n个的颜色组成，或者一个为n一个为n+1
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 #include <vector> 6 #include <algorithm> 7 using namespace std; 8 const int N = 100005; 9 10 int a[N] , max_id[N] , sec_id[N]; //a[]保存离散化后的c 11 12 struct Node{ 13 int v , num; 14 }; 15 16 vector<Node> vec[N]; 17 #define ll long long 18 ll max_val[N] , sec_val[N] , sum[N]; 19 20 struct Cube{ 21 int c , s , num; 22 bool operator<(const Cube &m)const{ 23 if(c == m.c) return s > m.s; 24 return c < m.c; 25 } 26 }cu[N]; 27 28 int bin_search(int x , int k) 29 { 30 int l=0 , r = k-1; 31 while(l<=r){ 32 int m=(l+r)>>1; 33 if(a[m] == x) return m; 34 else if(a[m]>x) r = m-1; 35 else l = m+1; 36 } 37 } 38 39 int main() 40 { 41 // freopen("a.in" , "r" , stdin); 42 int n; 43 while(scanf("%d" , &n ) == 1) 44 { 45 for(int i=0 ; i<=n ; i++) vec[i].clear(); 46 47 for(int i = 0 ;i<n ; i++) 48 { 49 scanf("%d%d" , &cu[i].c , &cu[i].s); 50 cu[i].num = i+1; 51 } 52 53 sort(cu , cu+n); 54 int k = 0; 55 a[k++] = cu[0].c; 56 for(int i=1 ; i<n ; i++){ 57 if(cu[i].c != cu[i-1].c) a[k++] = cu[i].c; 58 } 59 60 memset(sum , 0 , sizeof(sum)); 61 memset(max_val , 0 , sizeof(max_val)); 62 memset(sec_val , 0 , sizeof(sec_val)); 63 for(int i=0 ; i<n ; i++){ 64 int index = bin_search(cu[i].c , k); 65 Node node; 66 node.num = cu[i].num , node.v = cu[i].s; 67 vec[index].push_back(node); 68 sum[index] = sum[index] + cu[i].s; 69 int len = vec[index].size(); 70 if(max_val[len] < sum[index]){ 71 sec_val[len] = max_val[len]; 72 sec_id[len] = max_id[len]; 73 74 max_val[len] = sum[index]; 75 max_id[len] = index; 76 } 77 else if(sec_val[len] < sum[index]){ 78 sec_val[len] = sum[index]; 79 sec_id[len] = index; 80 } 81 } 82 // cout<<"test: "<<max_val[1]<<" index: "<<max_id[1]<<" "<<sec_id[1]<<endl; 83 int col1 , col2 , len1 , len2; 84 ll ans = 0; 85 for(int len=1 ; len<=n ; len++){ 86 if(max_val[len] && sec_val[len]){ 87 if(max_id[len] != sec_id[len]){ 88 if(ans < max_val[len]+sec_val[len]){ 89 ans = max_val[len]+sec_val[len]; 90 col1 = max_id[len]; 91 col2 = sec_id[len]; 92 len1 = len , len2 = len; 93 } 94 } 95 } 96 if(max_val[len] && max_val[len+1]){ 97 if(max_id[len] != max_id[len+1]){ 98 if(ans < max_val[len]+max_val[len+1]){ 99 ans = max_val[len]+max_val[len+1];100 col1 = max_id[len];101 col2 = max_id[len+1];102 len1 = len , len2 = len+1;103 }104 }105 }106 if(sec_val[len] && max_val[len+1]){107 if(sec_id[len] != max_id[len+1]){108 if(ans < sec_val[len]+max_val[len+1]){109 ans = sec_val[len]+max_val[len+1];110 col1 = sec_id[len];111 col2 = max_id[len+1];112 len1 = len , len2 = len+1;113 }114 }115 }116 if(max_val[len] && sec_val[len+1]){117 if(max_id[len] != sec_id[len+1]){118 if(ans < max_val[len]+sec_val[len+1]){119 ans = max_val[len]+sec_val[len+1];120 col1 = max_id[len];121 col2 = sec_id[len+1];122 len1 = len , len2 = len+1;123 }124 }125 }126 }127 128 printf("%I64d\n%d\n" , ans , len1+len2);129 printf("%d" , vec[col2][0].num);130 for(int i=0 ; i<len1 ; i++){131 printf(" %d" , vec[col1][i].num);132 if(i+1<len2) printf(" %d" , vec[col2][i+1].num);133 }134 puts("");135 }136 return 0;137 }
寒假训练2解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。