mmpT1数据错了。。。
你是能看到第一题的 friends呢。
—— hja
?座楼房,立于城中 。
第?座楼,高度 ℎ?。
你需要一开始选择座楼,跳。 在第 ?座楼准备跳需要 ??的花费。 每次可以跳到任何一个还没有过的楼上去。但是代价,另外一座楼的代价是两高度差绝对值 ,最后一次从楼上跳到地面不需 要代价(只能跳到地上一次)。为在不超过 要代价(只能跳到地上一次)。为在不超过 ?的情况下,最多跳几次楼。 (一座楼 只能 跳一次 ,且每次 跳楼 都要 计算 准备 的花费 )
输入格式:
第一行个整数 ?,代表 楼的数量。
接下来一行 ?个整数代表 ??。
接下来一行 ?个整数代表 ℎ?。
最后一行个整数 ?。
输出格式:
一行个整数 代表答案 。
输入样例#1
4
3 5 4 11
2 1
3 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<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<ctime>
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<b.c;
25 }
26 int comp2(const node &a,const node &b)
27 {
28 return a.h<b.h;
29 }
30 int ans=0;
31 int vis[MAXN];
32 int T;
33 int dfs(int now,int spend,int have)
34 {
35 ans=max(ans,have);
36 for(int i=1;i<=n;i++)
37 {
38 if(vis[i]==0&&spend+a[i].c+abs(a[now].h-a[i].h)<=T)
39 {
40 if(clock()-bg>=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 }
正解:
1(by myl)
考虑跳楼的集合
一定会有∑Ci
按照高度排序
高度差的代价==h5-h1
枚举最矮的楼,最高的楼
按照C排序,一个一个的选
总花费Hj-Hi+Ci+Cj+∑选出来的Ci<=T的最大值 复杂度:O(N^3logN)
2(by zhx)
dp
按照从低向高排序
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 <vector>
2 #include <list>
3 #include <map>
4 #include <set>
5 #include <queue>
6 #include <deque>
7 #include <stack>
8 #include <bitset>
9 #include <algorithm>
10 #include <functional>
11 #include <numeric>
12 #include <utility>
13 #include <sstream>
14 #include <iostream>
15 #include <iomanip>
16 #include <cstdio>
17 #include <cmath>
18 #include <cstdlib>
19 #include <ctime>
20 #include<cstring>
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<a.t;
37 }
38 }z[100];
39
40 class GUMIAndSongsDiv1 {
41 public:
42 int maxSongs(vector <int> duration, vector <int> tone, int T) {
43 int n=duration.size();
44 for (int a=0;a<n;a++)
45 z[a]=rec(duration[a],tone[a]);
46 sort(z,z+n);
47 memset(f,0x3f,sizeof(f));
48 f[0][0]=0;
49 f[0][1]=z[0].d;
50 for (int a=1;a<n;a++)
51 for (int b=0;b<=a+1;b++)
52 if (!b) f[a][b]=0;
53 else
54 {
55 for (int c=0;c<a;c++)
56 f[a][b]=min(f[a][b],f[c][b-1]+z[a].d+(b==1 ? 0 : z[a].t-z[c].t));
57 }
58 int ans=0;
59 for (int a=0;a<n;a++)
60 for (int b=1;b<=n;b++)
61 if (f[a][b]<=T) ans=max(ans,b);
62 return ans;
63
64 }
65 };
66
67
68 //<%: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 <int> p0, vector <int> 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<int> duration;
126 vector<int> 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 <int> p0;
151 vector <int> 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
你是能看到第二题的 friends呢。
—— laekov
塔立于都市, 攀登上塔,能够到达更远的地方。但是需要破解谜 题。仍然有 ?个数,但并不给你 而是了?×?−12个数,代表它们两的 和。那么,这 ?个数是多少呢?
输入格式:
一行个整数 ?。
接下来一行 ?×?−12个数,代表两之和。
输出格式:
第一行个整数 ?代表解的个数 。
接下来 ?行 ,每行 ,每?个数代表一组解,从小到大排列。的顺序 按照字典个数代表一组解,从小到大排列。的顺序 按照字典个数代表一组解,从小到大排列。的顺序 按照字典从大到小排列。
输入样例#1:
4
3 5 4 7 6 5
输出样例#1:
1
1 2 3 4
输入样例#2:
4
11 17 21 12 20 15
输出样例#2:
2
4 7 8 13
3 8 9 12
P104 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<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<algorithm>
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<a;c++)
30 {
31 if (res[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 }
你是能看到第三题的 friends呢。
—— aoao
街上的灯亮起,指引向着远方路 街上的灯亮起,指引向着远方路 街上的灯亮起,指引向着远方路 街上的灯亮起,指引向着远方路 街上的灯亮起,指引向着远方路 。每个街灯上都有一数, 每个街灯上都有一数, 每个街灯上都有一数, 每个街灯上都有一数, 每次询问, 每次询问, 第?个街灯到第 ?个街灯上的数模 ?等于 ?的有几个。
输入格式:
第一行两个数 ?,?,代表街灯的个数 和询问。
接下来一行 ?个数,代表 街灯上的数。
接下来 ?行,每四个数 ?,?,?,?代表一组询问。
输出格式:
对于每次询问,输出一行代表答案 。
输入样例#1: 1 5 2 3 7 1 3 2 2 5 3 0
输出样例#1:
2
1
对于 30%的数据, 1≤?,?≤103。
对于另外 30%的 数据,每次询问?一样。
对于 100%的数据, 1≤?,?≤105,街灯上的数不超过 104,1≤?≤109。
30分是暴力
另外30分可以用莫队水。。
但是标程是用链表做的
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<map>
6 #include<algorithm>
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 node
19 {
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<int,int>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]<base[b.r];
33 else return base[a.l]<base[b.l];
34 }
35 inline void dele(int pos)
36 {
37 happen[a[pos]%mod]--;
38 }
39 inline void add(int pos)
40 {
41 happen[a[pos]%mod]++;
42 }
43 inline void modui()
44 {
45 int ll=0,rr=-1;
46 int now=0;
47 for(int i=1;i<=m;i++)
48 {
49 while(ll<q[i].l) dele(ll),ll++;
50 while(ll>q[i].l) add(ll-1),ll--;
51 while(rr<q[i].r) add(rr+1),rr++;
52 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<int,int>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分
暴力
60
把%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 <cstdio>
2 #include <cstring>
3 #include <algorithm>
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 else
80 printf("%d\n", querya(l, r, p, k));
81 }
82 }