Codeforces Round #434 (Div. 2, )-字典树&好题&板子-Polycarp's phone book（字典树详解）

25-03-12 9

最近很多小伙伴都在问CodeforcesRound#434(Div.2,)-字典树&好题&板子-Polycarp'sphonebook和字典树详解这两个问题，那么本篇文章就来给大家详细解答一下，同时本

最近很多小伙伴都在问Codeforces Round #434 (Div. 2, )-字典树&好题&板子-Polycarp's phone book和字典树详解这两个问题，那么本篇文章就来给大家详细解答一下，同时本文还将给你拓展Analyzing Polyline -- Codeforces Round #123 (Div. 2)、C. Book Reading （Codeforces Round #582 (Div. 3)）、Codeforces 1005D Polycarp and Div 3、Codeforces 1082 A. Vasya and Book - 题意 (Educational Codeforces Round 55 (Rated for Div. 2))等相关知识，下面开始了哦！

本文目录一览：

Codeforces Round #434 (Div. 2, )-字典树&好题&板子-Polycarp's phone book（字典树详解）
Analyzing Polyline -- Codeforces Round #123 (Div. 2)
C. Book Reading （Codeforces Round #582 (Div. 3)）
Codeforces 1005D Polycarp and Div 3
Codeforces 1082 A. Vasya and Book - 题意 (Educational Codeforces Round 55 (Rated for Div. 2))

Codeforces Round #434 (Div. 2, )-字典树&好题&板子-Polycarp's phone book（字典树详解）

总结

以上是小编为你收集整理的Codeforces Round #434 (Div. 2, )-字典树&好题&板子-Polycarp''s phone book全部内容。

如果觉得小编网站内容还不错，欢迎将小编网站推荐给好友。

Analyzing Polyline -- Codeforces Round #123 (Div. 2)

题意：https://codeforc.es/problemset/problem/195/D

求折线段数。

思路：

对pos进行sort，对不同区间段加k，两个dp处理不同k>0 or k<0前后缀，判断即可。

注意：long double，ESP=1e-20。

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\\Users\\13606\\Desktop\\草稿.txt","r",stdin);
  6 #include <bitset>
  7 //#include <map>
  8 //#include<unordered_map>
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr
 13 #include <string>
 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int,vector<int>,greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first,nth,last,compare)
 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 23 #define fo(a,b,c) for(register int a=b;a<=c;++a)
 24 #define fr(a,c) for(register int a=b;a>=c;--a)
 25 #define mem(a,b) memset(a,sizeof(a))
 26 #define pr printf
 27 #define sc scanf
 28 #define ls rt<<1
 29 #define rs rt<<1|1
 30 typedef long long ll;
 31 #define RG register int;
 32 void swapp(int &a,int &b);
 33 double fabss(double a);
 34 int maxx(int a,int b);
 35 int minn(int a,int b);
 36 int Del_bit_1(int n);
 37 int lowbit(int n);
 38 int abss(int a);
 39 //const long long INF=(1LL<<60);
 40 const double E=2.718281828;
 41 const double PI=acos(-1.0);
 42 const int inf=(1<<30);
 43 const double ESP=1e-20;
 44 const int mod=(int)1e9+7;
 45 const int N=(int)1e6+10;
 46 
 47 struct node
 48 {
 49     int k,id;
 50     long double pos;
 51     friend bool operator<(node a,node b)
 52     {
 53         return a.pos<b.pos;
 54     }
 55 }a[N];
 56 
 57 long double get(int k,int b)
 58 {
 59     long double len=1.0*b/(1.0*k);
 60     len=abs(len);
 61     if(k>0)
 62     {
 63         if(b>0)
 64             return -len;
 65         else
 66             return len;
 67     }
 68     else
 69     {
 70         if(b>0)
 71             return len;
 72         else
 73             return -len;
 74     }
 75 }
 76 bool same(long double x,long double y)
 77 {
 78     return abs(x-y)<ESP;
 79 }
 80 
 81 ll dp[N],dp2[N];
 82 
 83 int main()
 84 {
 85     int n,cnt=0;
 86     long double xx;
 87     sc("%d",&n);
 88     for(int i=1;i<=n;++i)
 89     {
 90         int k,b;
 91         sc("%d%d",&k,&b);
 92         if(k==0)
 93             continue;
 94         a[++cnt]={k,b},a[cnt].pos=get(a[cnt].k,a[cnt].b);
 95     }
 96     n=cnt;
 97     sort(a+1,a+1+n);
 98     a[1].id=1;
 99     int id=1;
100     for(int i=2;i<=n;++i)
101     {
102         if(!same(a[i].pos,a[i-1].pos))
103             id++;
104         a[i].id=id;
105     }
106     for(int i=1;i<=n;++i)
107         if(a[i].k>0)
108             dp[a[i].id]+=a[i].k;
109     for(int i=1;i<=n;++i)
110         dp[i]+=dp[i-1];
111     for(int i=n;i>=1;--i)
112     {
113         if(a[i].k<0)
114             dp2[a[i].id-1]+=a[i].k;
115     }
116     for(int i=n;i>=0;--i)
117         dp2[i]+=dp2[i+1];
118     int ans=0;
119     for(int i=1;i<=id;++i)
120         if(dp[i]+dp2[i]!=dp[i-1]+dp2[i-1])
121             ans++;
122     pr("%d\n",ans);
123     return 0;
124 }
125 
126 /**************************************************************************************/
127 
128 int maxx(int a,int b)
129 {
130     return a>b?a:b;
131 }
132 
133 void swapp(int &a,int &b)
134 {
135     a^=b^=a^=b;
136 }
137 
138 int lowbit(int n)
139 {
140     return n&(-n);
141 }
142 
143 int Del_bit_1(int n)
144 {
145     return n&(n-1);
146 }
147 
148 int abss(int a)
149 {
150     return a>0?a:-a;
151 }
152 
153 double fabss(double a)
154 {
155     return a>0?a:-a;
156 }
157 
158 int minn(int a,int b)
159 {
160     return a<b?a:b;
161 }

C. Book Reading （Codeforces Round #582 (Div. 3)）

polycarp is reading a book consisting of $n$

Your task is to calculate the sum of all digits polycarp has written down.

You have to answer $q$

Input

The first line of the input contains one integer $q$

The following $q$

Output

For each query print the answer for it — the sum of digits written down by polycarp.

Example

input

copy

7
1 1
10 1
100 3
1024 14
998244353 1337
123 144
1234312817382646 13

output

copy

1
45
153
294
3359835
0
427262129093995

分析：计算出n范围内m的个位数的倍数的个位数的和

#include <bits/stdc++.h>
 
#define TOP 10001
 
using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(0); cin.tie(0); map<int,vector<int> > r; int q; ll m,n,coc,rest,fin,ans; vector<int> aux; r[1] = {1,2,3,4,5,6,7,8,9,0}; r[2] = {2,0}; r[3] = {3,1,0}; r[4] = {4,0}; r[5] = {5,0}; r[6] = {6,0}; r[7] = {7,0}; r[8] = {8,0}; r[9] = {9,0}; cin >> q; while(q--){ cin >> n >> m; coc = n / m; fin = m % 10; ans = 0; if(fin != 0){ aux = r[fin]; n = aux.size(); rest = coc % n; coc /= n; for(int i = 0; i < n; ++i) ans += aux[i] * (coc + (i < rest)); } cout << ans << ‘\n‘; } return 0; }

Codeforces 1005D Polycarp and Div 3

dp[i]表示前i个数最多能分成多少块%3为0，nxt[x]表示x这个上一次出现的位置。首先想到 $ dp[i] = max(dp[j]) + 1, (sum[i]-sum[j]) mod 3 == 0$，然后注意到他一定是从最近的那个满足条件的位置，也就是nxt[i]转移过来的，因为相比之前的位置这样一定不会更糟，所以方程就是 $ dp[i] = max( dp[nxt[i]] + 1, dp[i-1]) $ 还有一个点就是如果当前位置模3为0，那么dp[i]一定大于1，忘了这个转移结果一致直WA，早点拍就好了。

#include <bits/stdc++.h>
#define pb push_back
const long double PI = acos(-1.0);
const long double eps = 0.000001;
using namespace std;
int n,m,nxt[5],dp[222222];
char s[222222];
//174094882455171152761423221685761
int main() {
    scanf(" %s",s);
    n = strlen(s);
    memset(nxt,-1,sizeof(nxt));
    int sum = 0;
    dp[0]=((s[0]-''0'')%3==0);
    sum += (s[0]-''0'');sum%=3;
    nxt[sum]=0;
    for(int i = 1; i < n; ++i) {
        int x = s[i] - ''0'';
        sum = (sum + x)%3;
        dp[i] = dp[i-1];
        if(sum==0)dp[i]=max(dp[i],1);
        if(nxt[sum]!=-1) dp[i] = max(dp[nxt[sum]] + 1,dp[i]);
        nxt[sum]=i;
    }
    printf("%d\n",dp[n-1]);
    return 0;
}

Codeforces 1082 A. Vasya and Book - 题意 (Educational Codeforces Round 55 (Rated for Div. 2))

A. Vasya and Book

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Vasya is reading a e-book. The file of the book consists of nn pages, numbered from 11 to nn. The screen is currently displaying the contents of page xx, and Vasya wants to read the page yy. There are two buttons on the book which allow Vasya to scroll dd pages forwards or backwards (but he cannot scroll outside the book). For example, if the book consists of 1010 pages, and d=3d=3, then from the first page Vasya can scroll to the first or to the fourth page by pressing one of the buttons; from the second page — to the first or to the fifth; from the sixth page — to the third or to the ninth; from the eighth — to the fifth or to the tenth.

Help Vasya to calculate the minimum number of times he needs to press a button to move to page yy.

Input

The first line contains one integer tt (1≤t≤1031≤t≤103) — the number of testcases.

Each testcase is denoted by a line containing four integers nn, xx, yy, dd (1≤n,d≤1091≤n,d≤109, 1≤x,y≤n1≤x,y≤n) — the number of pages, the starting page, the desired page, and the number of pages scrolled by pressing one button, respectively.

Output

Print one line for each test.

If Vasya can move from page xx to page yy, print the minimum number of times he needs to press a button to do it. Otherwise print −1−1.

Example

input

Copy

output

Copy

4
-1
5

Note

In the first test case the optimal sequence is: 4→2→1→3→54→2→1→3→5.

In the second test case it is possible to get to pages 11 and 55.

In the third test case the optimal sequence is: 4→7→10→13→16→194→7→10→13→16→19.

翻到头只能从头翻，翻到尾只能从尾倒着翻。

代码:

 1 //A
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn=1e5+10;
 6 const int inf=0x3f3f3f3f;
 7 
 8 int main()
 9 {
10     int t;
11     cin>>t;
12     while(t--){
13         int n,x,y,d,ans=inf;
14         cin>>n>>x>>y>>d;
15         if(abs(y-x)%d==0) {ans=min(ans,abs(y-x)/d);}
16         if((y-1)%d==0) {ans=min(ans,x/d+(y-1)/d+(x%d==0?0:1));}
17         if((n-y)%d==0) {ans=min(ans,(n-x)/d+(n-y)/d+((n-x)%d==0?0:1));}
18         if(ans==inf) cout<<-1<<endl;
19         else cout<<ans<<endl;
20     }
21 }

关于Codeforces Round #434 (Div. 2, )-字典树&好题&板子-Polycarp's phone book和字典树详解的问题我们已经讲解完毕，感谢您的阅读，如果还想了解更多关于Analyzing Polyline -- Codeforces Round #123 (Div. 2)、C. Book Reading （Codeforces Round #582 (Div. 3)）、Codeforces 1005D Polycarp and Div 3、Codeforces 1082 A. Vasya and Book - 题意 (Educational Codeforces Round 55 (Rated for Div. 2))等相关内容，可以在本站寻找。

本文标签：