1729 单词查找树

三千年NOI全国比赛

时限: 2 s

空间范围: 127000 KB

标题等级 : 大师 Master

 

 

 

 

题材叙述 Description

在拓展文法分析的时候,通常须要检测贰个单词是不是在大家的单词列表里。为了抓实查找和定点的进度,平常都要画出与单词列表所对应的单词查找树,其性状如下:

l  根节点不分包字母,除根节点外每2个节点都仅蕴涵1个大写英文字母;


从根节点到某一节点,路径上经过的假名逐再三再四起来所组成的字母体系,称为该节点对应的单词。单词列表中的每一个词,都以该单词查找树有些节点所对应的单词;

l  在满足上述原则下,该单词查找树的节点数最少。

对3个分明的单词列表,请计算对应的单词查找树的节点数(包涵根节点)

 

输入描述 Input Description

该公文为3个单词列表,每一行仅包蕴三个单词和二个换行/回车符。每一种单词仅由大写的英文字符组成,长度不超过6三个字符。文件总参谋长度不超越32K,至少有一行数据。

输出描述 Output Description

该文件中仅包蕴八个平头和二个换行/回车符。该整数为单词列表对应的单词查找树的节点数。

样例输入 Sample Input

A

AN

ASP

AS

ASC

ASCII

BAS

BASIC

样例输出 Sample Output

13

数量范围及提醒 Data Size & Hint

 

分析:

先是要对建树的进度有1个打听。对于如今被拍卖的单词和当下树:在根结点的子结点中找单词的率先位字母,若存在则随之在该结点的子结点中搜寻第①位……如此下来直到单词截止,即不要求在该树中添加结点;或单词的第n位无法被找到,即将单词的第n位及之后的字母顺序参与单词查找树中去。但,本难点只是问您结点总数,而非建树方案,且有32K文本,所以理应考虑能还是不能够不经过建树就直接算出结点数?为了表达难点的本质,大家提交二个概念:二个单词相对于另三个单词的差:设单词1的长度为L,且与单词2从第N位初阶不雷同,则说单词1针锋相对于单词2的差为L-N+1,那是讲述单词相似程度的量。可知,将贰个单词参预单词树的时候,须到场的结点数等于该单词树中已有单词的差的相当的小值。

   
单词的字典顺序排列后的行列则有所类似的性状,即在二个字典顺序体系中,第m个单词相对于第m-3个单词的差必定是它对于前m-一个单词的差中细小的。于是,得出建树的一律算法:

① 读入文件;

② 对单词列表举办字典顺序排序;


依次总计每一个单词对前一单词的差,并把差加上起来。注意:第二个单词相对于“空”的差为该单词的长短;


累加和再加上1(根结点),输出结果。

就给定的样例,依照这么些算法求结点数的进度如下表:

图片 1

 

 

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 string a[10001];
 7 int tot=1;
 8 int main()
 9 {
10     int n=1;
11     while(cin>>a[n])
12     n++;
13     sort(a+1,a+n+1);
14     int l=a[1].length();
15     for(int i=2;i<=n;i++)
16     {
17         int j=0;
18         while(a[i][j]==a[i-1][j]&&j<a[i].length())
19         {
20             j++;
21         }
22         tot=tot+(a[i].length()-j);
23     }
24     cout<<tot;
25     return 0;
26 }

 

展望分数:100+0+60=160

实际上分数:100+0+60=160

mmpT1数据错了。。。

 

T1遭遇

题材叙述

您是能旁观第1题的 friends呢。

—— hja

?座楼宇,立于城中 。

第?座楼,高度 ℎ?。

您要求一发端选取座楼,跳。 在第 ?座楼准备跳要求 ??的消费。
每一次能够跳到其它一个还并未过的楼上去。然则代价,其它一座楼的代价是两冲天差相对值
,最后叁遍从楼上跳到地面不需 要代价(只好跳到地上一回)。为在不超越要代价(只可以跳到地上三次)。为在不超越 ?的动静下,最多跳一回楼。
(一座楼 只可以 跳1遍 ,且每一次 跳楼 都要 总计 准备 的开支 )

输入输出格式

输入格式:

 

先是行个整数 ?,代表 楼的数据。

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

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

说到底一行个整数 ?。

 

输出格式:

 

一行个整数 代表答案 。

 

输入输出样例

输入样例#1: 复制

4
3 5 4 11
2 1
3 17

输出样例#1: 复制

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

说明

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

对于其余 二成的数目,全体 ℎ?相同。

对此此外 1/5的多少, ??=0。

P104 zhx 遭遇

第 3 页 共 6 页

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

 

不会做,可是七拾六分的算法貌似比较好想

可是h相等的情形相似写炸了,。。。

 

图片 2图片 3

  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排序,三个二个的选

style=”font-size: 14pt;”>总开销Hj-Hi+Ci+Cj+∑选出来的Ci<=T的最大值

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

2(by zhx)

dp

安分守己从低向高排序

style=”font-size: 14pt;”>$f[i][j]$表示停留在i,已经跳了j栋楼,的小不点儿费用

枚举下3次跳哪栋楼

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

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

统计答案的时候枚举i,j观看是不是<=T

 

 

图片 4图片 5

  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

鬼畜的正解

 

 

T2都市

题材叙述

您是能见到第贰题的 friends呢。

—— laekov

塔立于城市, 攀登上塔,能够到达更远的地方。可是急需破解谜 题。还是有
?个数,但并不给你 而是了?×?−11个数,代表它们两的 和。那么,那?个数是多少吧?

输入输出格式

输入格式:

 

一行个整数 ?。

接下去一行 ?×?−十一个数,代表两之和。

 

输出格式:

 

率先行个整数 ?代表解的个数 。

接下去 ?行 ,每行 ,每?个数代表一组解,从小到大排列。的相继
依照字典个数代表一组解,从小到大排列。的一一
根据字典个数代表一组解,从小到大排列。的各样 依据字典从大到小排列。

 

输入输出样例

输入样例#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 页

说明

对于 三成的数量, 1≤?≤5,?个数均不超越 10。

对此 百分之六十的多少, 1≤?≤50,?个数均不抢先 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)$

 

图片 6图片 7

 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 }

View Code

 

 

 

 

T3街灯

题材叙述

您是能看到第叁题的 friends呢。

—— aoao

街上的灯亮起,教导向着远处路 街上的灯亮起,引导向着天涯路
街上的灯亮起,携带向着角落路 街上的灯亮起,引导向着角落路
街上的灯亮起,指导向着远处路 。每一种街灯上都有一数, 各种街灯上都有一数,
每一个街灯上都有一数, 每一种街灯上都有一数, 每趟询问, 每一回询问,
第?个街灯到第 ?个街灯上的数模 ?等于 ?的有多少个。

输入输出格式

输入格式:

 

首先行多个数 ?,?,代表街灯的个数 和精晓。

接下去一行 ?个数,代表 街灯上的数。

接下去 ?行,每多个数 ?,?,?,?代表一组精晓。

 

出口格式:

 

对此每一遍询问,输出一行代表答案 。

 

输入输出样例

输入样例#1: 复制

5 2
1 5 2 3 7
1
3 2 2 5 3 0

出口样例#1: 复制

2
1

说明

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

对此其余 3/10的 数据,每回询问?一样。

对于 百分百的数额, 1≤?,?≤105,街灯上的数不当先 104,1≤?≤109。

 

三十二分是强力

其它二十7分能够用莫队水。。

可是标程是用链表做的

图片 8图片 9

 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对于每1个询问预处理

p>100

考虑a[i]%p==v

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

枚举k,k<=100

 

图片 10图片 11

 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 }

正解