Day2上午解题报告

阅读量：6095 次

发布时间：2019-06-20

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

预计分数：100+0+60=160

实际分数：100+0+60=160

mmpT1数据错了。。。

T1遭遇

题目描述

你是能看到第一题的 friends呢。

—— hja

?座楼房，立于城中。

第?座楼，高度 ℎ?。

你需要一开始选择座楼，跳。在第 ?座楼准备跳需要 ??的花费。每次可以跳到任何一个还没有过的楼上去。但是代价，另外一座楼的代价是两高度差绝对值，最后一次从楼上跳到地面不需要代价（只能跳到地上一次）。为在不超过要代价（只能跳到地上一次）。为在不超过 ?的情况下，最多跳几次楼。（一座楼只能跳一次，且每次跳楼都要计算准备的花费）

输入输出格式

输入格式：

第一行个整数 ?，代表楼的数量。

接下来一行 ?个整数代表 ??。

接下来一行 ?个整数代表 ℎ?。

最后一行个整数 ?。

输出格式：

一行个整数代表答案。

输入输出样例

输入样例#1：

43 5 4 112 13 17

输出样例#1：

3【样例解释】从1号楼跳到 2号楼再跳到 3号楼是一种 可行 的方案 。

说明

对于 30%的数据， 1≤?≤5。

对于另外 20%的数据，所有 ℎ?相同。

对于另外 20%的数据， ??=0。

P104 zhx 遭遇

第 3 页共 6 页

对于 100%的数据， 1≤?≤50,1≤??,ℎ?≤106,1≤?≤107。

不会做，不过70分的算法貌似比较好想

但是h相等的情况貌似写炸了，。。。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 const int MAXN=101; 9 const int INF=0x7ffff; 10 inline int read() 11 { 12 char c=getchar();int flag=1,x=0; 13 while(c<'0'||c>'9') { if(c=='-') flag=-1;c=getchar();} 14 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag; 15 } 16 int n,bg;//kashi 17 struct node 18 { 19 int c; 20 int h; 21 }a[MAXN]; 22 int comp(const node &a,const node &b) 23 { 24 return a.c
            
             =900) 41 { 42 printf("%d",ans); 43 exit(0); 44 } 45 vis[i]=1; 46 dfs(i,spend+a[i].c+abs(a[now].h-a[i].h),have+1); 47 vis[i]=0; 48 } 49 } 50 } 51 int flagh=1;//高度是否相同 52 int flagc=1;//花费是否都为0 53 inline void solvec()//花费都为0 54 { 55 sort(a+1,a+n+1,comp2); 56 for(int i=1;i<=n;i++)//从每一个点往后跳 57 { 58 int nowjump=0; 59 int nowspend=0; 60 for(int j=i+1;j<=n;j++) 61 { 62 63 if(abs(a[j].h-a[j-1].h)+nowspend<=T) 64 { 65 nowspend=abs(a[j].h-a[j-1].h)+nowspend; 66 nowjump+=1; 67 } 68 ans=max(ans,nowjump+1); 69 } 70 } 71 } 72 inline void solveh() 73 { 74 int nowjump=0; 75 int nowspend=-1; 76 if(a[1].c<=T) 77 { 78 nowspend=a[1].c; 79 for(int i=2;i<=n;i++) 80 if(nowspend+a[i].c<=T) 81 nowjump++,nowspend+=a[i].c; 82 } 83 84 if(nowspend!=-1) ans=max(ans,nowjump+1); 85 } 86 int main() 87 { 88 // freopen("meet.in","r",stdin); 89 // freopen("meet.out","w",stdout); 90 bg=clock(); 91 n=read(); 92 for(int i=1;i<=n;i++) a[i].c=read(); 93 for(int i=1;i<=n;i++) a[i].h=read(); 94 T=read(); 95 sort(a+1,a+n+1,comp); 96 for(int i=1;i<=n;i++) 97 if(a[i].c!=0) flagc=0; 98 for(int i=1;i<=n;i++) 99 for(int j=1;j<=n;j++) 100 if(a[i].h!=a[j].h&&i!=j)101 flagh=0;102 if(flagc) solvec();103 if(flagh) solveh();104 105 for(int i=1;i<=n;i++)106 if(a[i].c<=T) 107 vis[i]=1,dfs(i,a[i].c,1);108 printf("%d",ans);109 return 0;110 }

莫名其妙丢20分

正解：

1(by myl)

考虑跳楼的集合

一定会有∑Ci

按照高度排序

高度差的代价==h5-h1

枚举最矮的楼，最高的楼

按照C排序，一个一个的选

总花费Hj-Hi+Ci+Cj+∑选出来的Ci<=T的最大值

复杂度:$O(N^3logN)$

2(by zhx)

按照从低向高排序

$f[i][j]$表示停留在i，已经跳了j栋楼，的最小花费

枚举下一次跳哪栋楼

$f[k][i+1]=min( f[k][j+1],f[i][j]+C[k]+abs(hk-hi) )$

复杂度:$O(n^3)$

统计答案的时候枚举i，j观察是否<=T

1 #include 
      
         2 #include 
       
          3 #include 
          4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 #include 
                   
                     15 #include 
                    
                      16 #include 
                     
                       17 #include 
                      
                        18 #include 
                       
                         19 #include 
                        
                          20 #include
                         
                           21 22 using namespace std; 23 24 int f[100][100]; 25 26 struct rec 27 { 28 int d,t; 29 rec(){} 30 rec(int a,int b) 31 { 32 d=a;t=b; 33 } 34 bool operator<(const rec &a)const 35 { 36 return t

duration, vector

tone, int T) { 43 int n=duration.size(); 44 for (int a=0;a

<%:testing-code%> 69 //Powered by KawigiEdit 2.1.4 (beta) modified by pivanof! 70 // BEGIN KAWIGIEDIT TESTING 71 // Generated by KawigiEdit 2.1.4 (beta) modified by pivanof 72 bool KawigiEdit_RunTest(int testNum, vector

p0, vector

p1, int p2, bool hasAnswer, int p3) { 73 cout << "Test " << testNum << ": [" << "{ "; 74 for (int i = 0; int(p0.size()) > i; ++i) { 75 if (i > 0) { 76 cout << ","; 77 } 78 cout << p0[i]; 79 } 80 cout << "}" << "," << "{ "; 81 for (int i = 0; int(p1.size()) > i; ++i) { 82 if (i > 0) { 83 cout << ","; 84 } 85 cout << p1[i]; 86 } 87 cout << "}" << "," << p2; 88 cout << "]" << endl; 89 GUMIAndSongsDiv1 *obj; 90 int answer; 91 obj = new GUMIAndSongsDiv1(); 92 clock_t startTime = clock(); 93 answer = obj->maxSongs(p0, p1, p2); 94 clock_t endTime = clock(); 95 delete obj; 96 bool res; 97 res = true; 98 cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl; 99 if (hasAnswer) {100 cout << "Desired answer:" << endl;101 cout << "\t" << p3 << endl;102 }103 cout << "Your answer:" << endl;104 cout << "\t" << answer << endl;105 if (hasAnswer) {106 res = answer == p3;107 }108 if (!res) {109 cout << "DOESN'T MATCH!!!!" << endl;110 } else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {111 cout << "FAIL the timeout" << endl;112 res = false;113 } else if (hasAnswer) {114 cout << "Match :-)" << endl;115 } else {116 cout << "OK, but is it right?" << endl;117 }118 cout << "" << endl;119 return res;120 }121 int main() {122 freopen("meet.in","r",stdin);123 freopen("meet.out","w",stdout);124 125 vector

duration;126 vector

tone;127 int n,T;128 scanf("%d",&n);129 for (int a=1;a<=n;a++)130 {131 int v;132 scanf("%d",&v);133 duration.push_back(v);134 }135 for (int a=1;a<=n;a++)136 {137 int v;138 scanf("%d",&v);139 tone.push_back(v);140 }141 scanf("%d",&T);142 GUMIAndSongsDiv1 *obj;143 int answer;144 obj = new GUMIAndSongsDiv1();145 answer = obj->maxSongs(duration, tone, T);146 printf("%d\n",answer);147 /*bool all_right;148 all_right = true;149 150 vector

p0;151 vector

p1;152 int p2;153 int p3;154 155 {156 // ----- test 0 -----157 int t0[] = {3,5,4,11};158 p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));159 int t1[] = {2,1,3,1};160 p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));161 p2 = 17;162 p3 = 3;163 all_right = KawigiEdit_RunTest(0, p0, p1, p2, true, p3) && all_right;164 // ------------------165 }166 167 {168 // ----- test 1 -----169 int t0[] = {100,200,300};170 p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));171 int t1[] = {1,2,3};172 p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));173 p2 = 99;174 p3 = 0;175 all_right = KawigiEdit_RunTest(1, p0, p1, p2, true, p3) && all_right;176 // ------------------177 }178 179 {180 // ----- test 2 -----181 int t0[] = {1,2,3,4};182 p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));183 int t1[] = {1,1,1,1};184 p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));185 p2 = 100;186 p3 = 4;187 all_right = KawigiEdit_RunTest(2, p0, p1, p2, true, p3) && all_right;188 // ------------------189 }190 191 {192 // ----- test 3 -----193 int t0[] = {9,11,13,17};194 p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));195 int t1[] = {2,1,3,4};196 p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));197 p2 = 20;198 p3 = 1;199 all_right = KawigiEdit_RunTest(3, p0, p1, p2, true, p3) && all_right;200 // ------------------201 }202 203 {204 // ----- test 4 -----205 int t0[] = {87,21,20,73,97,57,12,80,86,97,98,85,41,12,89,15,41,17,68,37,21,1,9,65,4,67,38,91,46,82,7,98,21,70,99,41,21,65,11,1,8,12,77,62,52,69,56,33,98,97};206 p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));207 int t1[] = {88,27,89,2,96,32,4,93,89,50,58,70,15,48,31,2,27,20,31,3,23,86,69,12,59,61,85,67,77,34,29,3,75,42,50,37,56,45,51,68,89,17,4,47,9,14,29,59,43,3};208 p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));209 p2 = 212;210 p3 = 12;211 all_right = KawigiEdit_RunTest(4, p0, p1, p2, true, p3) && all_right;212 // ------------------213 }214 215 if (all_right) {216 cout << "You're a stud (at least on the example cases)!" << endl;217 } else {218 cout << "Some of the test cases had errors." << endl;219 }220 return 0;*/221 }222 // END KAWIGIEDIT TESTING

鬼畜的正解

T2都市

题目描述

你是能看到第二题的 friends呢。

—— laekov

塔立于都市，攀登上塔，能够到达更远的地方。但是需要破解谜题。仍然有 ?个数，但并不给你而是了?×?−12个数，代表它们两的和。那么，这 ?个数是多少呢？

输入输出格式

输入格式：

一行个整数 ?。

接下来一行 ?×?−12个数，代表两之和。

输出格式：

第一行个整数 ?代表解的个数。

接下来 ?行，每行，每?个数代表一组解，从小到大排列。的顺序按照字典个数代表一组解，从小到大排列。的顺序按照字典个数代表一组解，从小到大排列。的顺序按照字典从大到小排列。

输入输出样例

输入样例#1：

43 5 4 7 6 5

输出样例#1：

11 2 3 4

输入样例#2：

411 17 21 12 20 15

输出样例#2：

24 7 8 133 8 9 12P104 zhx 都市第 5 页 共 6 页

说明

对于 30%的数据， 1≤?≤5，?个数均不超过 10。

对于 60%的数据， 1≤?≤50，?个数均不超过 100。

对于 100%的数据， 1≤?≤300，?个数均不超过 108。

不会做，

最后没时间了，连暴力都没打。

正解

先对给出以及枚举的数的数进行排序

设枚举的数为$a_1,a_2$

给出的数为$b_1,b_2$

性质：

a1+a2==b1

a1+a3==b2

设a2+a3=x

枚举a2+a3等于b里面的哪个数

对于所有的ai，都进行这个操作

每次解除a1,a2,a3

时间复杂度:$O(n^4)≈O(n^3)$

1 v#include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7  8 const int maxn=310; 9 10 int n,m,res[maxn],ans[maxn][maxn],z[maxn*maxn],cnt;11 12 bool use[maxn*maxn];13 14 void check(int p)15 {16     memset(use,false,sizeof(use));17     if ((z[1]+z[2]+z[p])&1) return;18     res[1]=(z[1]+z[2]+z[p])/2-z[p];19     res[2]=z[1]-res[1];20     res[3]=z[2]-res[1];21     use[1]=use[2]=use[p]=true;22     for (int a=4,b=3;a<=n;a++)23     {24         while (b<=m && use[b])25             b++;26         if (b>m) return;27         res[a]=z[b]-res[1];28         use[b]=true;29         for (int c=2;c
          
           res[a]) return;32             int v=res[c]+res[a];33             int p=lower_bound(z+1,z+m+1,v)-z;34             if (z[p]!=v) return;35             int px=p;36             while (px && z[px]==z[p])37                 px--;38             px++;39             while (px<=m && z[px]==z[p] && use[px])40                 px++;41             if (z[px]!=z[p] || use[px]) return;42             p=px;43             use[p]=true;44         }45     }46     cnt++;47     for (int a=1;a<=n;a++)48         ans[cnt][a]=res[a];49 }50 51 int main()52 {53     freopen("city.in","r",stdin);54     freopen("city.out","w",stdout);55 56     scanf("%d",&n);57     m=n*(n-1)/2;58     for (int a=1;a<=m;a++)59         scanf("%d",&z[a]);60     sort(z+1,z+m+1);61     for (int a=3;a<=m;)62     {63         check(a);64         int b=a;65         while (b<=m && z[b]==z[a])66             b++;67         a=b;68     }69     printf("%d\n",cnt);70     for (int a=1;a<=cnt;a++)71         for (int b=1;b<=n;b++)72         {73             printf("%d",ans[a][b]);74             if (b==n) printf("\n");75             else printf(" ");76         }77 78     return 0;79 }

View Code

T3街灯

题目描述

你是能看到第三题的 friends呢。

—— aoao

街上的灯亮起，指引向着远方路街上的灯亮起，指引向着远方路街上的灯亮起，指引向着远方路街上的灯亮起，指引向着远方路街上的灯亮起，指引向着远方路。每个街灯上都有一数，每个街灯上都有一数，每个街灯上都有一数，每个街灯上都有一数，每次询问，每次询问，第?个街灯到第 ?个街灯上的数模 ?等于 ?的有几个。

输入输出格式

输入格式：

第一行两个数 ?,?，代表街灯的个数和询问。

接下来一行 ?个数，代表街灯上的数。

接下来 ?行，每四个数 ?,?,?,?代表一组询问。

输出格式：

对于每次询问，输出一行代表答案。

输入输出样例

输入样例#1：

5 21 5 2 3 713 2 2 5 3 0

输出样例#1：

说明

对于 30%的数据， 1≤?,?≤103。

对于另外 30%的数据，每次询问?一样。

对于 100%的数据， 1≤?,?≤105，街灯上的数不超过 104，1≤?≤109。

30分是暴力

另外30分可以用莫队水。。

但是标程是用链表做的

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
           6 #include
           
             7 using namespace std; 8 const int MAXN=1e6; 9 const int INF=0x7ffff;10 inline int read()11 {12 char c=getchar();int flag=1,x=0;13 while(c<'0'||c>'9') { if(c=='-') flag=-1;c=getchar();}14 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;15 }16 int n,m;17 int a[MAXN];18 struct node19 {20 int l,r,p,v,id;21 }q[MAXN];22 int out[MAXN];23 int flag=1;//p是否都相等 24 int ansout=0;25 int mod=0;26 int base[MAXN];27 //map
            
             happen;28 int happen[2*MAXN*10+10];29 int comp(const node &a,const node &b)30 {31 if(base[a.l]==base[b.l])32 return base[a.r]
             
              q[i].l) add(ll-1),ll--;51 while(rr
              
               q[i].r) dele(rr),rr--;53 out[q[i].id]=happen[q[i].v];54 }55 for(int i=1;i<=m;i++)56 printf("%d\n",out[i]);57 }58 int main()59 {60 // freopen("light.in","r",stdin);61 // freopen("light.out","w",stdout);62 n=read(),m=read();63 int p=sqrt(n);64 for(int i=1;i<=n;i++) base[i]=(i-1)/p;65 for(int i=1;i<=n;i++) a[i]=read();66 for(int i=1;i<=m;i++)67 {68 q[i].l=read();69 q[i].r=read();70 q[i].p=read();71 q[i].v=read();72 q[i].id=i;73 if(i>=2&&q[i].p!=q[i-1].p) flag=0;74 }75 if(flag&&n>=1e3&&m>=1e3)76 {77 sort(q+1,q+m+1,comp);78 mod=q[1].p;79 static map
               
                happen;80 modui();81 return 0;82 }83 for(int i=1;i<=m;i++)84 {85 int ans=0;86 for(int j=q[i].l;j<=q[i].r;j++)87 if(a[j]%q[i].p==q[i].v)88 ans++;89 printf("%d\n",ans);90 }91 return 0;92 }

莫队

30分

暴力

把%p的余数扔到vector||链表||某个数据结构中

每次二分出l的位置和r的位置

空间复杂度:$O(N)$

100

对p分块

p<=100对于每一个询问预处理

p>100

考虑a[i]%p==v

的值为v+p.v+kp。。

枚举k，k<=100

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 using namespace std; 6  7 const int maxn = 100009; 8 const int maxv = 10000; 9 const int bsz = 100;10 const int maxb = 103;11 12 int n, m;13 int a[maxn], vb[maxb][maxb], ve[maxb][maxb];14 int xb[maxn], xe[maxn];15 int i_buf[maxn * maxb * 2], tib;16 17 void pre() {18     memset(ve, 0, sizeof(ve));19     memset(xe, 0, sizeof(xe));20     for (int i = 1; i <= n; ++ i)21         ++ xe[a[i]];22     for (int i = 0; i <= maxv; ++ i) {23         xb[i] = tib;24         tib += xe[i];25         xe[i] = xb[i];26     }27     for (int i = 1; i <= n; ++ i)28         i_buf[xe[a[i]] ++] = i;29     for (int m = 1; m <= bsz; ++ m) {30         for (int i = 1; i <= n; ++ i)31             ++ ve[m][a[i] % m];32         for (int i = 0; i < m; ++ i) {33             vb[m][i] = tib;34             tib += ve[m][i];35             ve[m][i] = vb[m][i];36         }37         for (int i = 1; i <= n; ++ i)38             i_buf[ve[m][a[i] % m] ++] = i;39     }40 }41 42 int queryb(int l0, int r0, int p, int k) {43     if (vb[p][k] == ve[p][k])44         return 0;45     int *x1 = lower_bound(i_buf + vb[p][k], i_buf + ve[p][k], l0);46     int *x2 = upper_bound(i_buf + vb[p][k], i_buf + ve[p][k], r0);47     return x2 - x1;48 }49 50 int querys(int v, int l0, int r0) {51     if (xb[v] == xe[v])52         return 0;53     int *x1 = lower_bound(i_buf + xb[v], i_buf + xe[v], l0);54     int *x2 = upper_bound(i_buf + xb[v], i_buf + xe[v], r0);55     return x2 - x1;56 }57 58 int querya(int l0, int r0, int p, int k) {59     int ans = 0;60     for (int i = k; i <= maxv; i += p)61         ans += querys(i, l0, r0);62     return ans;63 }64 65 int main() {66     freopen("light.in", "r", stdin);67     freopen("light.out", "w", stdout);68 69     scanf("%d%d", &n, &m);70     tib = 0;71     for (int i = 1; i <= n; ++ i)72         scanf("%d", a + i);73     pre();74     while (m --) {75         int l, r, p, k;76         scanf("%d%d%d%d", &l, &r, &p, &k);77         if (p <= bsz)78             printf("%d\n", queryb(l, r, p, k));79         else80             printf("%d\n", querya(l, r, p, k));81     }82 }

正解

转载地址：http://krgwa.baihongyu.com/

你可能感兴趣的文章

宝宝树11年创业纪录片曝光王怀南：他们不知道我的厉害

查看>>

快手首次透露商业化布局：将重点发力短视频广告

查看>>

点融任命崔亚文为执行总裁和联席董事长郭宇航彻底淡出

查看>>

中消协：警惕以治病为噱头的保健品虚假宣传行为

查看>>

河南外贸总值首破5500亿元对中东欧16国贸易大增