虽然普及组一般都是暴力省一，但是有一些题目还是挺难的qwq个人觉得能进TG的题目会在前面打上'*'
NOIP2002(clear)
#include<bits/stdc++.h>
using namespace std;
int main(){
std::ios::sync_with_stdio(false);
;
;
cin >> k;
while(Sn <= k) Sn += 1.0 / i++;
cout << --i;
;
}
级数求和
//递推
#include<bits/stdc++.h>
using namespace std;
][];
][] = {,,,-,-,,-,-,,,,-,-,-,-,};
int main()
{
ios::sync_with_stdio(false);
int a , b , c , d;
cin >> a >> b >> c >> d;
; i <= a ; i++)
; j <= b ; j++)
{
;
; k < && f ; k++)
] == i && d + dir[k][] == j) f = ;
if(f && (c != i || d != j))
: ][j] + num[i][j ? j - : ];
;
}
cout << num[a][b];
;
}
过河卒
//递归
#include<bits/stdc++.h>
using namespace std;
] , cou , n;
];
bool ifZ(int a)
{
|| !a) return false;
; i * i <= a ; i++)
) return false;
return true;
}
void dfs(int a , int b , int c)
{
if(!a)
{
if(ifZ(b)) cou++;
return;
}
for(int i = c ; i <= n - a ; i++)
if(!vis[i])
{
vis[i] = ;
dfs(a - , b + num[i] , i + );
vis[i] = ;
}
}
int main()
{
std::ios::sync_with_stdio(false);
int k;
cin >> n >> k;
; i < n ; i++) cin >> num[i];
dfs(k , , );
cout << cou;
;
}
选数
//按位搜索
#include<bits/stdc++.h>
using namespace std;
multimap < char , char > rule;
][];
] = { , };
int dfs(char a , int b)
{
;
times[b][a - ;
;
map < char , char > :: iterator iter = rule.find(a);
; i != rule.count(a) ; ++i , ++iter)
sum += dfs(iter -> second , b);
return sum;
}
int main()
{
string s;
int n;
for(cin >> s >> n ; n ; n--){
char a , b;
cin >> a >> b;
rule.insert(make_pair(a , b));
}
; i < s.size() ; i++)
{
int k = dfs(s[i] , i);
; i <= num[] ; i++) num[i] *= k;
; i <= num[] ; i++)
)
{
num[i + ] += num[i] / ;
num[i] %= ;
]) num[]++;
}
}
]--) cout << num[num[] + ];
;
}
产生数
NOIP2003(clear)
//卡特兰数
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll fast_read()
{
char c = getchar();
ll a = ;
;
while(!isdigit(c))
{
;
c = getchar();
}
) + (a << ) + c - ' , c = getchar();
return k ? -a : a;
}
inline void fast_print(ll x)
{
] , dirN = -;
) putchar('-') , x = -x;
, x /= ;
) putchar(');
) putchar(num[dirN--] + );
putchar('\n');
}
] = { , };
int main()
{
int n = fast_read();
; i <= n ; i++)
; j < n ; j++)
num[i] += num[j] * num[i - j - ];
cout << num[n];
;
}
栈
//注意最后的0:0
#include<bits/stdc++.h>
using namespace std;
][];
int main()
{
string s;
, L11 = , W21 = , L21 = , dirA = ;
while(cin >> s)
{
;
; i < s.size() && !ifE ; i++)
{
if(s[i] == 'W')
{
W11++;
W21++;
&& W11 - L11 >= )
{
cout << W11 << ":" << L11 << endl;
W11 = L11 = ;
}
&& W21 - L21 >= )
{
ans[dirA][] = W21;
ans[dirA++][] = L21;
W21 = L21 = ;
}
}
else if(s[i] == 'L')
{
L11++;
L21++;
&& L11 - W11 >= )
{
cout << W11 << ":" << L11 << endl;
W11 = L11 = ;
}
&& L21 - W21 >= )
{
ans[dirA][] = W21;
ans[dirA++][] = L21;
W21 = L21 = ;
}
}
;
}
if(ifE) break;
}
cout << W11 << ":" << L11 << endl;
; i < dirA ; i++) cout << endl << ans[i][] << ];
cout << endl << W21 << ":" << L21;
;
}
乒乓球
//区间DP
#include<bits/stdc++.h>
using namespace std;
] , maxN[][][] , minN[][][];
inline int max(int a , int b){
return a > b ? a : b;
}
inline int min(int a , int b){
return a < b ? a : b;
}
int main(){
memset(minN , 0x3f , sizeof(minN));
int N , M;
cin >> N >> M;
; i <= N ; i++)
{
cin >> num[i];
num[i + N] = num[i];
}
; i <= N << ; i++)
; j++)
minN[i][j][] = maxN[i][j][]
= ((maxN[i][j - ][] + num[j]) % + ) % ;
; k <= M ; k++)
; i <= (N << ) - k + ; i++)
; j <= N << && j - i + <= N ; j++)
for(int m = i ; m < j ; m++)
, k - j + m) ; n < k && n <= m - i + ; n++)
{
maxN[i][j][k] = max(maxN[i][j][k] , maxN[i][m][n] * maxN[m + ][j][k - n]);
minN[i][j][k] = min(minN[i][j][k] , minN[i][m][n] * minN[m + ][j][k - n]);
}
, minM = 0x3f3f3f3f;
; i <= N ; i++)
{
maxM = max(maxM , maxN[i][i + N - ][M]);
minM = min(minM , minN[i][i + N - ][M]);
}
cout << minM << endl << maxM;
;
}
数字游戏
//第一问用对数函数得答案，第二问高精快速幂
#include<bits/stdc++.h>
using namespace std;
] = { , } , num2[] , num3[] = { , };
int main()
{
std::ios::sync_with_stdio(false);
int p;
cin >> p;
cout << floor(log10() * p + ) << endl;
while(p)
{
)
{
; i <= ; i++)
; j <= - i ; j++)
{
num2[i + j - ] += num1[i] * num3[j];
] >= )
{
< ) num2[i + j] += num2[i + j - ] / ;
num2[i + j - ] %= ;
}
}
; i ; i--)
{
num3[i] = num2[i];
num2[i] = ;
}
}
; i <= ; i++)
; j <= - i ; j++)
{
num2[i + j - ] += num1[i] * num1[j];
] >= )
{
< ) num2[i + j] += num2[i + j - ] / ;
num2[i + j - ] %= ;
}
}
; i ; i--)
{
num1[i] = num2[i];
num2[i] = ;
}
p >>= ;
}
num3[]--;
; i ; i--)
{
cout << num3[i];
) % == ) cout << endl;
}
;
}
麦森数
NOIP2004(clear)
#include<bits/stdc++.h>
using namespace std;
int main()
{
, maxD = ;
; i <= ; i++)
{
int a , b;
cin >> a >> b;
if(a + b > maxN)
{
maxN = a + b;
maxD = i;
}
}
cout << maxD;
;
}
不高兴的津津
//模拟
#include<bits/stdc++.h>
using namespace std;
struct hs{
int num , x , y;
}ans[];
bool cmp(hs a , hs b)
{
return a.num > b.num;
}
int main()
{
, i = , pri , nowX , nowY;
cin >> n >> m >> p;
; i <= n ; i++)
; j <= m ; j++)
{
int a;
cin >> a;
if(a)
{
ans[dirH].num = a;
ans[dirH].x = i;
ans[dirH++].y = j;
}
}
sort(ans , ans + dirH , cmp);
].x * + > p)
{
cout << ;
;
}
p -= ans[].x + ;
pri = ans[].num;
nowX = ans[].x;
nowY = ans[].y;
>= )
{
p -= abs(nowX - ans[i].x) + abs(nowY - ans[i].y) + ;
nowX = ans[i].x;
nowY = ans[i].y;
pri += ans[i++].num;
}
cout << pri;
;
}
花生采摘
//乱搞
#include<bits/stdc++.h>
using namespace std;
int n;
][];
void hx(int a , int b)
{
if(a == n) cout << m[a][b];
else{
hx(a + , * b);
hx(a + , * b + );
][ * b] == ][ * b + ] == 'B')
m[a][b] = 'B';
][ * b] == ][ * b + ] == 'I')
m[a][b] = 'I';
else m[a][b] = 'F';
cout << m[a][b];
}
}
int main()
{
string s;
cin >> n >> s;
; i < s.size() ; i++)
') m[n][i] = 'I';
else m[n][i] = 'B';
hx( , );
;
}
FBI树
//在这一道题中认识了next_permutation()
#include<bits/stdc++.h>
using namespace std;
];
int main()
{
int n , k;
cin >> n >> k;
; i < n ; i++) cin >> num[i];
; i < k ; i++) next_permutation(num , num + n);
; i < n ; i++) cout << num[i] << " ";
;
}
火星人
NOIP2005(clear)
#include<bits/stdc++.h>
using namespace std;
];
int main(){
; i < ; i++) cin >> num[i];
;
cin >> a;
; i < ; i++)
) cou++;
cout << cou;
;
}
陶陶摘苹果
//线段树练习题（划掉
#include<bits/stdc++.h>
using namespace std;
];
int main()
{
std::ios::sync_with_stdio(false);
;
for(cin >> L >> m ; m ; m--)
{
int a , b;
;
}
; L--) if(!vis[L]) cou++;
cout << cou;
;
}
校门外的树
//01背包
#include<bits/stdc++.h>
using namespace std;
];
int main(){
std::ios::sync_with_stdio(false);
int T , M;
for(cin >> T >> M ; M ; M--)
{
int a , b;
cin >> a >> b;
for(int i = T ; i >= a ; i--)
vis[i] = max(vis[i] , vis[i - a] + b);
}
cout << vis[T];
;
}
采药
//考虑第一位在多少步内完成循环，然后考虑后两位在多少步内完成循环，递推下去找到答案
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
int K;
struct Bignum{
];
Bignum(){
memset(a , , sizeof(a));
}
int& operator [](int x){
return a[x];
}
void input(){
string s;
cin >> s;
; i <= s.size() ; i++)
a[i] = s[s.size() - i] - ';
}
void output(){
] ; i ; i--)
putchar(a[i] + ');
}
Bignum operator *(Bignum b){
Bignum c;
c[] = K;
; i <= K ; i++)
; j <= K ; j++)
c[i + j - ] += a[i] * b[j];
; i <= K ; i++)
){
c[i + ] += c[i] / ;
c[i] %= ;
}
return c;
}
void operator *=(int b){
; i <= a[] ; i++)
a[i] *= b;
; i <= a[] ; i++)
){
a[i + ] += a[i] / ;
a[i] %= ;
])
++a[];
}
}
}ori , A , B , ans;
int main(){
#ifndef ONLINE_JUDGE
freopen("1050.in" , "r" , stdin);
//freopen("1050.out" , "w" , stdout);
#endif
ori.input();
cin >> K;
ori[] = K;
A = ori;
B = ori;
ans[] = ans[] = ;
; i <= K ; i++){
if((ori * A)[i] == ori[i])
continue;
B = A;
;
; !f && j <= ; j++){
A = A * B;
if((A * ori)[i] == ori[i]){
ans *= j + ;
f = ;
}
}
if(!f){
puts("-1");
;
}
}
ans.output();
;
}
*循环
NOIP2006(clear)
#include<bits/stdc++.h>
using namespace std;
];
int main()
{
;
cin >> n;
; i < n ; i++) cin >> num[i];
sort(num , num + n);
; i < n ; i++)
]) cou++;
cout << cou << endl << num[];
; i < n ; i++)
]) cout << " " << num[i];
;
}
明明的随机数
//又是01背包
#include<bits/stdc++.h>
using namespace std;
];
int main()
{
int n , t;
for(cin >> n >> t ; t ; t--)
{
int a , b;
cin >> a >> b;
; i--)
vis[i + a] = max(vis[i + a] , vis[i] + a * b);
}
cout << vis[n];
;
}
开心的金明
//模拟
#include<bits/stdc++.h>
using namespace std;
string now;
int s , t , w;
int check(){
int dir = w;
&& now[dir] - 'a' + (w - dir) == t)
dir--;
return dir;
}
int main()
{
cin >> s >> t >> w >> now;
s--;
t--;
w--;
; i <= ; i++){
int k = check();
)
;
now[k]++;
while(++k <= w)
now[k] = now[k - ] + ;
cout << now << endl;
}
;
}
Jam的计数法
//二进制相关
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll fast_read()
{
char c = getchar();
ll a = ;
;
while(!isdigit(c))
{
;
c = getchar();
}
) + (a << ) + c - ' , c = getchar();
return k ? -a : a;
}
inline void fast_print(ll x)
{
] , dirN = -;
) putchar('-') , x = -x;
, x /= ;
) putchar(');
) putchar(num[dirN--] + );
}
int main()
{
ll a = fast_read() , b = fast_read() , sum = , d = ;
while(b)
{
) sum += d;
b >>= ;
d *= a;
}
fast_print(sum);
;
}
数列
NOIP2007(clear)
//结构体排序
#include<bits/stdc++.h>
using namespace std;
struct stu{
int chi , math , eng , tot , i;
inline void input()
{
cin >> chi >> math >> eng;
tot = chi + math + eng;
}
}ans[];
bool cmp(stu a , stu b)
{
return a.tot > b.tot || a.tot == b.tot && a.chi > b.chi || a.tot == b.tot && a.chi == b.chi && a.i < b.i;
}
int main()
{
int n;
cin >> n;
; i < n ; i++)
{
ans[i].input();
ans[i].i = i + ;
}
sort(ans , ans + n , cmp);
; i < ; i++)
cout << ans[i].i << " " << ans[i].tot << endl;
;
}
奖学金
//贪心选能够搭配的最大的
#include<bits/stdc++.h>
using namespace std;
];
int main()
{
ios::sync_with_stdio(false);
, cou = ;
cin >> n >> k;
; i < k ; i++) cin >> num[i];
sort(num , num + --k + );
while(m <= k)
{
cou++;
int sum = num[k--];
while(sum + num[m] <= n && m <= k) sum += num[m++];
}
cout << cou;
;
}
纪念品分组
//条件判断练习题
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll fast_read()
{
char c = getchar();
ll a = ;
;
while(!isdigit(c))
{
;
c = getchar();
}
) + (a << ) + c - ' , c = getchar();
return k ? -a : a;
}
int main()
{
int M = fast_read() , S = fast_read() , T = fast_read() , t , s;
* >= S)
;
else cout << "Yes" << endl << (int)ceil(S / 60.0);
>= T) cout << ;
else{
t = M / ;
s = M / * ;
M %= ;
&& T - t >= ceil(( - M) / 4.0))
{
) M += ;
else{
M -= ;
s += ;
}
t++;
}
while(s < S && T > t)
- M) / )
{
t += ceil(( - M) / 4.0);
s += ;
}
else
{
- M) / - M) / < && S - s > ceil(( - M) / )
{
t += ceil(( - M) / 4.0);
s += ;
}
;
}
if(s >= S) cout << "Yes" << endl << t;
else cout << "No" << endl << s;
}
;
}
守望者的逃离
//递推
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll fast_read()
{
char c = getchar();
ll a = ;
;
while(!isdigit(c))
{
;
c = getchar();
}
) + (a << ) + c - ' , c = getchar();
return k ? -a : a;
}
inline void fast_print(ll x)
{
] , dirN = -;
) putchar('-') , x = -x;
, x /= ;
) putchar(');
) putchar(num[dirN--] + );
}
][];
int main()
{
int a = fast_read();
; i <= a ; i++)
{
num[i][] = num[i - ][] + ;
num[i][] = ;
; j <= num[i - ][] ; j++)
{
num[i][j] += num[i - ][j] * ;
)
{
num[i][j + ]++;
num[i][j] -= ;
}
}
]]) num[i][]--;
}
] ; i ; i--)
fast_print(num[a][i]);
;
}
Hanoi双塔问题
NOIP2008(clear)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a , b , c , a1;
char d;
scanf("%d-%d-%d-%c" , &a1 , &b , &c , &d);
a = a1 + b % * + b / % * + b / * + c % * + c / % * + c / % * + c / % * + c / * ;
== && d == == d - ') printf("Right");
== ? + ');
;
}
ISBN号码
//排序
#include<bits/stdc++.h>
using namespace std;
struct hl{
int i , num;
}h[] , l[];
bool cmp1(hl a , hl b)
{
return a.num > b.num;
}
bool cmp2(hl a , hl b)
{
return a.i < b.i;
}
int main()
{
ios::sync_with_stdio(false);
int n , m , k , q , d;
cin >> n >> m >> k >> q >> d;
; i <= n ; i++) h[i].i = i;
; i <= m ; i++) l[i].i = i;
; i < d ; i++)
{
int a , b , c , d;
cin >> a >> b >> c >> d;
if(a == c) l[min(b , d)].num++;
else h[min(a , c)].num++;
}
sort(h , h + n , cmp1);
sort(h , h + k , cmp2);
; i < k ; i++)
{
if(i) cout << " ";
cout << h[i].i;
}
cout << endl;
sort(l , l + m , cmp1);
sort(l , l + q , cmp2);
; i < q ; i++)
{
if(i) cout << " ";
cout << l[i].i;
}
;
}
排座椅
//递推
#include<bits/stdc++.h>
using namespace std;
][] = {};
int main(){
cin >> n >> k;
; i < k ; i++)
{
; j < n ; j++)
])
{
v[(j + ) % n][] += v[j][];
v[(j + n - ) % n][] += v[j][];
}
; j < n ; j++)
{
v[j][] = v[j][];
v[j][] = ;
}
}
cout << v[][];
;
}
传球游戏
//这个模拟可还行
#include<bits/stdc++.h>
using namespace std;
][];
][] = {"\0\0+---+" , "\0/ /|" , "+---+ |" , "| | +" , "| |/\0" , "+---+\0\0"
};
][];
int main(){
ios::sync_with_stdio(false);
memset(m , '.' , sizeof(m));
int a , b;
cin >> a >> b;
, l = b * + a * + ;
; i <= a ; i++)
; j <= b ; j++)
{
cin >> num[i][j];
k = max(k , * (a - i) + * num[i][j] + );
}
; i <= a ; i++)
; j <= b ; j++)
{
* j - + * (a - i) , h = k - * (a - i);
while(num[i][j]--){
; p <= h ; p++)
; q++)
+ p - h][q - l]) m[p][q] = ex[ + p - h][q - l];
h -= ;
}
}
; i <= k ; i++)
{
) cout << endl;
; j <= l ; j++) cout << m[i][j];
}
;
}
立体图
NOIP2009(clear)
//注意细节
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
; i--)
{
int a;
cin >> a;
if(!a) continue;
) cout << "+";
)
|| !i) cout << a;
else cout << "-";
;
if(i) cout << "x";
&& i) cout << "^" << i;
}
;
}
多项式输出
//排序
#include<bits/stdc++.h>
using namespace std;
struct can{
int bmh , score;
}ans[];
bool cmp(can a , can b)
{
if(a.score == b.score)
return a.bmh < b.bmh;
return a.score > b.score;
}
int main()
{
std::ios::sync_with_stdio(false);
int n , m;
cin >> n >> m;
; i < n ; i++)
cin >> ans[i].bmh >> ans[i].score;
sort(ans , ans + n , cmp);
m *= 1.5;
].score == ans[m].score) m++;
cout << ans[m - ].score << " " << m << endl;
; i < m ; i++) cout << ans[i].bmh << " " << ans[i].score << endl;
;
}
分数线划定
//筛质因数
#include<bits/stdc++.h>
#define inf 0x7fffffff
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
] , num[] , N , m1 , m2;
int main(){
#ifdef OJ
freopen("1069.in" , "r" , stdin);
//freopen("1069.out" , "w" , stdout);
#endif
N = read();
m1 = read();
m2 = read();
; i <= N ; i++)
num[i] = read();
; i * i <= m1 ; i++)
){
;
){
m1 /= i;
cnt++;
}
cnt *= m2;
; j <= N ; j++){
;
){
num[j] /= i;
++t;
}
if(!t)
maxN[j] = inf;
else
maxN[j] = max(maxN[j] , cnt / t + (cnt % t ? : ));
}
}
)
; j <= N ; j++){
;
){
num[j] /= m1;
++t;
}
if(!t)
maxN[j] = inf;
else
maxN[j] = max(maxN[j] , m2 / t + (m2 % t ? : ));
}
int ans = inf;
; i <= N ; i++)
ans = min(ans , maxN[i]);
cout << (ans == inf ? - : ans);
;
}
*细胞分裂
//三方过一千
#include<bits/stdc++.h>
using namespace std;
] , pri[][] , cost[];
int main(){
memset(dp , -0x3f , sizeof(dp));
dp[] = ;
int N , M , P;
cin >> N >> M >> P;
; i <= N ; i++)
; j <= M ; j++)
cin >> pri[i][j];
; i <= N ; i++)
cin >> cost[i];
; i < M ; i++)
; j <= N ; j++){
int t = j , sum = -cost[j];
; m <= P && m + i <= M ; m++){
dp[m + i] = max(dp[m + i] , dp[i] + (sum += pri[t][m + i]));
t = t % N + ;
}
}
cout << dp[M];
;
}
道路游戏
NOIP2010(clear)
#include<bits/stdc++.h>
using namespace std;
inline int count_num(int a){
;
while(a)
{
== ) sum++;
a /= ;
}
return sum;
}
int main(){
;
for(cin >> N >> M ; N <= M ; N++) sum += count_num(N);
cout << sum;
;
}
数字统计
//贪心
#include<iostream>
using namespace std;
int main()
{
, f = , m[] = {} , n[] = {} , nhead = ;
cin >> i >> j;
; k < i ; k++)
{
cin >> n[k];
if(nhead < j)
{
m[nhead] = n[nhead];
nhead++;
}
}
while(f != j)
{
t++;
f = ;
; k < j ; k++)
)
if(nhead < i)
{
m[k] = n[nhead];
nhead++;
}
else
f++;
}
cout << t;
;
}
接水问题
//贪心+DP
#include<bits/stdc++.h>
#define P pair < int , int >
using namespace std;
P dis[];
];
bool cmp(P a , P b){
return a.first < b.first;
}
inline int max(int a , int b){
return a > b ? a : b;
}
inline int min(int a , int b){
return a < b ? a : b;
}
int main()
{
ios::sync_with_stdio(false);
;
cin >> x1 >> y1 >> x2 >> y2 >> N;
; i <= N ; i++)
{
int a , b;
cin >> a >> b;
dis[i].first = (a - x1) * (a - x1) + (b - y1) * (b - y1);
dis[i].second = (a - x2) * (a - x2) + (b - y2) * (b - y2);
}
sort(dis + , dis + N + , cmp);
] , dis[i].second);
; i <= N ; i++)
].first)
minN = min(dis[i].first + maxN[i + ] , minN);
cout << minN;
;
}
导弹拦截
//震惊！puts("0")竟然没分！
//第二问贪心选择每行第二大的数中最大的那个
#include<bits/stdc++.h>
using namespace std;
][];
int main(){
, dirA , dirB , maxA = , maxDirA , maxB = , maxDirB;
cin >> N;
; i < N ; i++)
; j <= N ; j++)
{
cin >> num[i][j];
num[j][i] = num[i][j];
}
; i <= N ; i++)
{
, dir , mci = , dirci;
; j <= N ; j++)
if(i ^ j)
if(m < num[i][j])
{
mci = m;
m = num[i][j];
dirci = dir;
dir = j;
}
else if(mci < num[i][j])
{
mci = num[i][j];
dirci = j;
}
if(mci > maxN){
maxN = mci;
dirA = i;
dirB = dirci;
}
}
; i <= N ; i++)
if(i ^ dirA && i ^ dirB && maxA < num[dirA][i])
{
maxA = num[dirA][i];
maxDirA = i;
}
; i <= N ; i++)
if(i ^ dirB && i ^ dirA && i ^ maxDirA && maxB < num[dirB][i])
{
maxB = num[dirB][i];
maxDirB = i;
}
if(num[maxDirA][maxDirB] > num[dirA][dirB]){
cout << ;
;
}
; i <= N ; i++)
if(i ^ dirA && i ^ dirB && i ^ maxDirA && i ^ maxDirB && (num[i][maxDirA] > maxN || num[i][maxDirB] > maxN))
{
, mDir;
; j <= N ; j++)
if(j ^ dirA && j ^ dirB && j ^ maxDirA && j ^ maxDirB && j ^ i && m < num[i][j])
{
m = num[i][j];
mDir = j;
}
if(num[mDir][dirA] > m || num[mDir][dirB] > m)
{
cout << ;
;
}
}
cout << << endl << maxN;
;
}
三国游戏
NOIP2011(clear)
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
] == '-')
{
cout << '-';
s = , s.size() - );
}
;
for(int i = s.size() ; i ; i--)
] - ')
{
cout << s[i - ];
f = ;
}
;
}
数字反转
#include<bits/stdc++.h>
using namespace std;
] , s2[];
int l1 , l2;
inline bool cmp(int i)
{
; j < l1 ; j++)
if(s1[j] != s2[j + i]) return false;
return true;
}
int main()
{
, couF = -;
gets(s1);
gets(s2);
l1 = strlen(s1);
l2 = strlen(s2);
; i < l1 ; i++)
if(s1[i] >= 'A' && s1[i] <= 'Z') s1[i] += 'a' - 'A';
; i < l2 ; i++)
if(s2[i] >= 'A' && s2[i] <= 'Z') s2[i] += 'a' - 'A';
; i <= l2 - l1 ; i++)
] == ' ') && (i == l2 - l1 || s2[l1 + i] == ' '))
{
cou++;
) couF = i;
}
if(cou) cout << cou << " " << couF;
;
;
}
统计单词数
//归并排序
#include<bits/stdc++.h>
using namespace std;
struct can{
int sl , fs , i;
}ans[] , win[] , lose[];
int n;
void gb()
{
, dirB = ;
; i < * n ; i++)
if(dirA != n && (dirB == n || win[dirA].fs > lose[dirB].fs || win[dirA].fs == lose[dirB].fs && win[dirA].i < lose[dirB].i))
ans[i] = win[dirA++];
else ans[i] = lose[dirB++];
}
bool cmp(can a , can b)
{
return a.fs > b.fs || a.fs == b.fs && a.i < b.i;
}
int main()
{
ios::sync_with_stdio(false);
int r , q;
cin >> n >> r >> q;
; i < * n ; i++) cin >> ans[i].fs;
; i < * n ; i++)
{
cin >> ans[i].sl;
ans[i].i = i + ;
}
sort(ans , ans + n * , cmp);
while(r--)
{
; i < n ; i++)
{
].sl > ans[i * + ].sl)
{
win[i] = ans[i * ];
lose[i] = ans[i * + ];
}
else
{
win[i] = ans[i * + ];
lose[i] = ans[i * ];
}
win[i].fs++;
}
gb();
}
cout << ans[q - ].i;
;
}
瑞士轮
//栈
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
, MOD = ;
][] = { , , , , , , , };
] = "()+*" , str[MAXN];
] , pos[MAXN] , topSt , len , topPos;
map < char , int > m;
inline void pop(){
){
st[topSt - ][] = (st[topSt - ][] * (st[topSt][] + st[topSt][]) + st[topSt - ][] * st[topSt][]) % MOD;
st[topSt - ][] = st[topSt - ][] * st[topSt][] % MOD;
}
else{
st[topSt - ][] = (st[topSt - ][] * (st[topSt][] + st[topSt][]) + st[topSt - ][] * st[topSt][]) % MOD;
st[topSt - ][] = st[topSt - ][] * st[topSt][] % MOD;
}
topSt--;
topPos--;
}
void calc(){
; i <= len ; i++){
int t = m[str[i]];
&& str[i - ] != ')'){
st[++topSt][] = ;
st[topSt][] = ;
}
] > ysj[t][])
pop();
] == ysj[t][])
--topPos;
else
pos[++topPos] = t;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1310.in" , "r" , stdin);
//freopen("1310.out" , "w" , stdout);
#endif
m[;
m[;
m[;
m[;
len = read();
scanf();
str[++len] = ')';
str[] = '(';
calc();
printf(][]);
;
}
*表达式的值
NOIP2012(clear)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
; i * i <= n ; i++)
){
cout << n / i;
;
}
}
质因数分解
//模拟，注意转圈的加速
#include<bits/stdc++.h>
using namespace std;
, m[][][] , vis[];
int main(){
cin >> N >> M;
; i < N ; i++)
; j < M ; j++)
{
scanf(] , &m[i][j][]);
])
vis[i]++;
}
int a;
cin >> a;
; i < N - ; i++)
{
];
key = (key + k) % ;
k = k % vis[i];
if(!k)
] ; a--);
else
{
) % M)
]) k--;
a--;
}
a = (a + M) % M;
}
cout << (key + m[N - ][a][]) % ;
;
}
寻宝
//DP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll fast_read()
{
char c = getchar();
ll a = ;
;
while(!isdigit(c))
{
;
c = getchar();
}
) + (a << ) + c - ' , c = getchar();
return k ? -a : a;
}
inline void fast_print(ll x)
{
] , dirN = -;
) putchar('-') , x = -x;
, x /= ;
) putchar(');
) putchar(num[dirN--] + );
}
] = {};
int main()
{
int n = fast_read() , m = fast_read();
while(n--)
{
int a = fast_read();
; i >= ; i--)
if(way[i])
; j <= a && j + i <= m ; j++)
way[i + j] = (way[i] + way[i + j]) % ;
}
fast_print(way[m]);
;
}
摆花
//打表大法好啊
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
struct Edge{
int end , upEd , w;
}Ed[] , fanEd[];
priority_queue < pair < int , int > > q;
] , fanHead[] , minDis[] , cul[] , cntEd , cntFanEd , N , M , K , S , T , tar;
][] , vis[];
inline void addEd(Edge* Ed , int* head , int& cntEd , int a , int b , int c){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].w = c;
head[a] = cntEd;
}
void Dijk(){
q.push(make_pair( , T));
memset(minDis , 0x3f , sizeof(minDis));
minDis[T] = ;
while(!q.empty()){
pair < int , int > t = q.top();
q.pop();
if(minDis[t.second] < -t.first)
continue;
for(int i = fanHead[t.second] ; i ; i = fanEd[i].upEd)
if(minDis[fanEd[i].end] > minDis[t.second] + fanEd[i].w){
minDis[fanEd[i].end] = minDis[t.second] + fanEd[i].w;
q.push(make_pair(-minDis[fanEd[i].end] , fanEd[i].end));
}
}
}
bool dfs(int beg , int now){
if(minDis[beg] + now > tar)
;
if(vis[cul[beg]])
;
; i <= K ; i++)
if(no[cul[beg]][i] && vis[i])
;
if(beg == T){
tar = now;
;
}
vis[cul[beg]] = ;
for(int i = head[beg] ; i ; i = Ed[i].upEd)
if(dfs(Ed[i].end , now + Ed[i].w)){
vis[cul[beg]] = ;
;
}
vis[cul[beg]] = ;
;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1078.in" , "r" , stdin);
//freopen("1078.out" , "w" , stdout);
#endif
N = read();
K = read();
M = read();
){
puts("-1");
;
}
S = read();
T = read();
; i <= N ; i++)
cul[i] = read();
; i <= K ; i++)
; j <= K ; j++)
no[i][j] = read();
; i <= M ; i++){
int a = read() , b = read() , c = read();
addEd(Ed , head , cntEd , a , b , c);
addEd(Ed , head , cntEd , b , a , c);
addEd(fanEd , fanHead , cntFanEd , b , a , c);
addEd(fanEd , fanHead , cntFanEd , a , b , c);
}
Dijk();
, r = ;
while(l < r){
tar = (l + r) >> ;
dfs(S , ) ? r = tar : l = tar + ;
}
printf( ? - : r);
;
}
文化之旅
NOIP2013(clear)
//数位DP（划掉
#include<bits/stdc++.h>
using namespace std;
inline int cou(int a , int b)
{
;
while(a)
{
== b) sum++;
a /= ;
}
return sum;
}
int main()
{
;
cin >> a >> b;
; i <= a ; i++) sum += cou(i , b);
cout << sum;
;
}
计数问题
//栈
#include<bits/stdc++.h>
using namespace std;
string s;
];
];
int main()
{
cin >> s;
s += '@';
, head = ;
; i < s.size() ; i++)
if(isdigit(s[i]))
nowN = (nowN * + s[i] - ) % ;
else{
num[head] = nowN;
nowN = ;
] == '*'){
num[head - ] = num[head - ] * num[head] % ;
head--;
}
op[head++] = s[i];
}
; i < head ; i++)
num[] = (num[] + num[i]) % ;
cout << num[];
;
}
表达式求值
//贪心+DP
#include<bits/stdc++.h>
#define ll __int128
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
ll sum[MAXN] , spe[MAXN] , sco[MAXN] , maxSco , minN , maxN , maxSCO , N;
int main(){
#ifdef OJ
freopen("1982.in" , "r" , stdin);
//freopen("1982.out" , "w" , stdout);
#endif
N = read();
int P = read();
spe[] = -1ll << ;
; i <= N ; i++){
sum[i] = sum[i - ] + read();
spe[i] = max(spe[i - ] , sum[i] - minN);
minN = min(minN , sum[i]);
}
maxSCO = sco[] = spe[];
maxN = sco[] + spe[];
; i <= N ; i++){
sco[i] = maxN;
maxSCO = max(maxSCO , sco[i]);
maxN = max(maxN , sco[i] + spe[i]);
}
cout << (int)(maxSCO % P);
;
}
小朋友的数字
//拓扑排序+（可能的）优化连边
#include<bits/stdc++.h>
using namespace std;
inline int read(){
;
char c = getchar();
while(!isdigit(c)) c = getchar();
) + (a << ) + (c ^ ') , c = getchar();
return a;
}
inline int max(int a , int b){
return a > b ? a : b;
}
vector < ];
] , maxN[];
][];
int main(){
;
while(m--){
int k = read() , bef;
vector < int > s , g;
s.push_back(bef = read());
; i ^ k ; i++){
int a = read();
while(++bef ^ a){
g.push_back(bef);
; j ^ i ; j++)
if(!vis[bef][s[j]]){
vis[bef][s[j]] = vis[s[j]][bef] = ;
Ed[bef].push_back(s[j]);
in[s[j]]++;
}
}
s.push_back(bef);
a = g.size();
; j ^ a ; j++)
if(!vis[g[j]][bef])
{
vis[g[j]][bef] = vis[bef][g[j]] = ;
Ed[g[j]].push_back(bef);
in[bef]++;
}
}
}
queue < int > q;
; i <= n ; i++)
if(!in[i]){
maxN[i] = ;
q.push(i);
}
while(!q.empty()){
int t = q.front();
q.pop();
Max = max(Max , maxN[t]);
; i < Ed[t].size() ; i++)
if(!--in[Ed[t][i]]){
maxN[Ed[t][i]] = maxN[t] + ;
q.push(Ed[t][i]);
}
}
cout << Max;
;
}
*车站分级
NOIP2014(clear)
//枚举分母，找最靠近给出条件的分子
#include<bits/stdc++.h>
using namespace std;
int main()
{
, ansB;
cin >> A >> B >> L;
; i <= L ; i++){
int t = A * i / B;
if(t > L)
break;
if(t * B == A * i){
cout << t << ' ' << i;
;
}
t++;
if(t > L)
break;
if(!ansA){
ansA = t;
ansB = i;
}
else
if(ansA * i > ansB * t){
ansA = t;
ansB = i;
}
}
cout << ansA << ' ' << ansB;
;
}
比例简化
//桶排
#include<bits/stdc++.h>
using namespace std;
];
];
int main()
{
, maxN = ;
cin >> n;
; i < n ; i++)
{
int a;
cin >> a;
num[a]++;
maxN = maxN < a ? a : maxN;
}
; i <= maxN ; i++)
; j <= maxN ; j++)
if(num[i] && num[j] && !vis[i + j])
{
cou += num[i + j];
vis[i + j] = ;
}
cout << cou;
;
}
珠心算测验
//找规律
#include<bits/stdc++.h>
using namespace std;
int main()
{
, N , A , B;
cin >> N >> A >> B;
&& B != && A != N && B != N){
A--;
B--;
sum += (N - ) << ;
N -= ;
}
)
cout << sum + B;
else
if(B == N)
cout << sum + N - + A;
else
if(A == N)
cout << sum + ((N - ) << ) + (N - B + );
else
cout << sum + (N - ) * + (N - A + );
;
}
螺旋矩阵
//搜索+DP
#include<bits/stdc++.h>
using namespace std;
][] , choose[] , num[][] , N , M , R , C , lasAns = 0x3f3f3f3f;
inline int abs(int a){
? a : -a;
}
inline int calc(int bef , int now){
;
; i < R ; i++)
sum += abs(num[choose[i]][bef] - num[choose[i]][now]);
return sum;
}
inline int ask(int now){
;
; i < R - ; i++)
sum += abs(num[choose[i]][now] - num[choose[i + ]][now]);
return sum;
}
inline void DP(){
memset(minN , 0x3f , sizeof(minN));
; i <= M ; i++){
minN[i][] = ask(i);
; j ; j--){
int t = calc(i , j);
; k <= j + && k <= C ; k++)
minN[i][k] = min(minN[i][k] , minN[j][k - ] + t + minN[i][]);
}
}
for(int i = C ; i <= M ; i++)
lasAns = min(lasAns , minN[i][C]);
}
void dfs(int dir , int num){
if(num == R){
DP();
return;
}
< R)
return;
dfs(dir + , num);
choose[num++] = dir;
dfs(dir + , num);
}
int main()
{
cin >> N >> M >> R >> C;
; i <= N ; i++)
; j <= M ; j++){
cin >> num[i][j];
}
dfs( , );
cout << lasAns;
;
}
*子矩阵
NOIP2015(clear)
#include<bits/stdc++.h>
using namespace std;
int main(){
, n , sum = ;
cin >> n;
while(n >= cou){
sum += cou * cou;
n -= cou++;
}
cout << sum + cou * n;
;
}
金币
#include<bits/stdc++.h>
using namespace std;
][];
][] = {,,-,,,,,-,,,-,-,-,,,-};
int main()
{
int n , m;
cin >> n >> m;
; i <= n ; i++)
; j <= m ; j++)
cin >> bomb[i][j];
; i <= n ; i++){
; j <= m ; j++)
if(bomb[i][j] == '*') cout << '*';
else{
;
; k < ; k++)
]][j + dir[k][]] == '*')
cou++;
cout << cou;
}
cout << endl;
}
;
}
扫雷游戏
//分类+前缀和
#include<bits/stdc++.h>
#define MAXN 100001
#define MOD 10007
using namespace std;
] , num[MAXN][] , col[MAXN] , val[MAXN];
int main()
{
ios::sync_with_stdio();
cin.tie();
cout.tie();
;
cin >> n >> m;
; i <= n ; i++)
cin >> val[i];
; i <= n ; i++){
cin >> col[i];
num[col[i]][i & ]++;
sum[col[i]][i & ] = (sum[col[i]][i & ] + val[i]) % MOD;
}
; i <= n ; i++)
s += ((num[col[i]][i & ] - ) * val[i] + sum[col[i]][i & ]) % MOD * i % MOD;
cout << s % MOD;
;
}
求和
//贪心+线段树
#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lch (now << 1)
#define rch (now << 1 | 1)
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
;
struct node{
int maxN , maxD , mark;
}Tree[MAXN << ];
int num[MAXN] , S[MAXN] , N , fur;
inline void pushup(int now){
if(Tree[lch].maxN > Tree[rch].maxN){
Tree[now].maxN = Tree[lch].maxN;
Tree[now].maxD = Tree[lch].maxD;
}
else{
Tree[now].maxN = Tree[rch].maxN;
Tree[now].maxD = Tree[rch].maxD;
}
}
inline void pushdown(int now){
if(Tree[now].mark){
Tree[lch].mark += Tree[now].mark;
Tree[lch].maxN += Tree[now].mark;
Tree[rch].mark += Tree[now].mark;
Tree[rch].maxN += Tree[now].mark;
Tree[now].mark = ;
}
}
void init(int now , int l , int r){
if(l == r){
Tree[now].maxD = l;
Tree[now].maxN = num[l] + (S[l] << );
}
else{
init(lch , l , mid);
init(rch , mid + , r);
pushup(now);
}
}
void change(int now , int l , int r , int tar , int num){
if(l == r){
Tree[now].maxN = num;
return;
}
pushdown(now);
if(mid >= tar)
change(lch , l , mid , tar , num);
else
change(rch , mid + , r , tar , num);
pushup(now);
}
void add(int now , int l , int r , int L , int R , int mark){
if(l >= L && r <= R){
Tree[now].mark += mark;
Tree[now].maxN += mark;
return;
}
pushdown(now);
if(mid >= L)
add(lch , l , mid , L , R , mark);
if(mid < R)
add(rch , mid + , r , L , R , mark);
pushup(now);
}
int main(){
#ifdef OJ
freopen("2672.in" , "r" , stdin);
//freopen("2672.out" , "w" , stdout);
#endif
N = read();
; i <= N ; i++)
S[i] = read();
; i <= N ; i++)
num[i] = read();
init( , , N);
;
; i <= N ; i++){
printf(].maxN);
].maxD;
; j < t ; j++)
change( , , N , j , num[j]);
if(t > fur){
add( , , N , t , N , -(S[t] - S[fur]) << );
fur = t;
}
change( , , N , t , );
}
;
}
*推销员
NOIP2016(clear)
#include<bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
, a , b;
cin >> k;
; i < ; i++)
{
cin >> a >> b;
minN = min(minN , (k / a + (k % a != )) * b);
}
cout << minN;
;
}
买铅笔
//随便枚举
#include<bits/stdc++.h>
using namespace std;
int main(){
;
cin >> n >> m;
, j = ; i + j < ; j++)
{
&& (i == || i == || i == || i == || i == || i == || i == ) || j == && (i == || i == || i == || i == ) || j == && i == )
{
j = ;
i++;
}
)
{
* + j / * + i % * + i / * + i * + j;
if(y >= n && y <= m)
num++;
}
}
cout << num;
;
}
回文日期
//双指针优化枚举
#include<bits/stdc++.h>
#define MAXN 100001
using namespace std;
int appear[MAXN] , t[MAXN] , k[MAXN];
vector < int > peo[MAXN];
int main()
{
ios::sync_with_stdio();
cin.tie();
cout.tie();
, N , dir = ;
cin >> N;
; i <= N ; i++){
cin >> t[i] >> k[i];
; j < k[i] ; j++){
int a;
cin >> a;
peo[i].push_back(a);
if(!appear[a]++)
ans++;
}
){
; j < k[dir] ; j++)
if(!--appear[peo[dir][j]])
ans--;
dir++;
}
cout << ans << endl;
}
;
}
海港
//换元、前缀和优化
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
] , num[] , A[] , B[] , C[] , D[];
int main(){
#ifndef ONLINE_JUDGE
freopen("2119.in" , "r" , stdin);
//freopen("2119.out" , "w" , stdout);
#endif
int N = read() , M = read();
; i <= M ; i++)
++pot[num[i] = read()];
; i * < N ; i++){
;
* i + ; d <= N ; d++){
int c = d - i;
sum += pot[d - * i - ] * pot[d - * i - ];
C[c] += sum * pot[d];
D[d] += sum * pot[c];
}
sum = ;
* i - ; a ; a--){
* i;
sum += pot[b + * i + ] * pot[b + * i + ];
B[b] += sum * pot[a];
A[a] += sum * pot[b];
}
}
; i <= M ; i++)
printf("%d %d %d %d\n" , A[num[i]] , B[num[i]] , C[num[i]] , D[num[i]]);
;
}
*魔法阵
NOIP2017(clear)
#include<bits/stdc++.h>
using namespace std;
int main(){
int a , b , c;
cin >> a >> b >> c;
cout << a / + b / * + c / ;
;
}
成绩
#include<bits/stdc++.h>
using namespace std;
];
int main()
{
int n , q;
cin >> n >> q;
; i <= n ; i++)
cin >> book[i];
sort(book + , book + n + );
while(q--){
int l , a , i;
cin >> l >> a;
l = pow( , l);
; i <= n ; i++)
if(book[i] % l == a)
break;
)
cout << - << endl;
else
cout << book[i] << endl;
}
;
}
图书管理员
//瞎搞图论
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define X now.x + dir[i][0]
#define Y now.y + dir[i][1]
//This code is written by Itst
using namespace std;
inline int read(){
;
;
char c = getchar();
while(c != EOF && !isdigit(c)){
if(c == '-')
f = ;
c = getchar();
}
while(c != EOF && isdigit(c)){
a = (a << ) + (a << ) + (c ^ ');
c = getchar();
}
return f ? -a : a;
}
struct node{
int x , y , col;
}now;
][] = { , , , - , , , - , };
][][] , col[][] , M , N;
queue < node > q;
void SPFA(){
memset(minDis , 0x3f , sizeof(minDis));
minDis[][][col[][]] = ;
q.push((node){ , , col[][]});
while(!q.empty()){
now = q.front();
q.pop();
; i < ; i++)
)
if(col[X][Y] || col[now.x][now.y]){
if(col[X][Y]){
if(minDis[X][Y][col[X][Y]] > minDis[now.x][now.y][now.col] + (now.col != col[X][Y])){
minDis[X][Y][col[X][Y]] = minDis[now.x][now.y][now.col] + (now.col != col[X][Y]);
q.push((node){X , Y , col[X][Y]});
}
}
else{
col[X][Y] = now.col;
){
minDis[X][Y][col[X][Y]] = minDis[now.x][now.y][now.col] + ;
q.push((node){X , Y , col[X][Y]});
}
col[X][Y] = ;
}
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("3956.in" , "r" , stdin);
//freopen("3956.out" , "w" , stdout);
#endif
memset(col , - , sizeof(col));
M = read();
N = read();
; i <= M ; i++)
; j <= M ; j++)
col[i][j] = ;
while(N--){
;
col[a][b] = c;
}
SPFA();
] == inf && minDis[M][M][] == inf && minDis[M][M][] == inf)
puts("-1");
else
printf(] , min(minDis[M][M][] , minDis[M][M][])));
;
}
棋盘
//二分答案、单调队列优化DP
#include<bits/stdc++.h>
#define MAXN 500002
using namespace std;
inline int read(){
;
;
char c = getchar();
while(!isdigit(c)){
;
c = getchar();
}
) + a + (c ^ ') , c = getchar();
return f ? -a : a;
}
inline int max(int a , int b){return a > b ? a : b;}
] , maxN[MAXN] , N , d , K;
bool vis[MAXN];
bool check(int mid){
deque < int > q;
, r = ;
; i <= N && ALLmax < K ; i++){
] - num[r][] > d + mid) r++;
] - num[r][] >= max(d - mid , ) && num[i][] - num[r][] <= d + mid){
if(vis[r]){
while(!q.empty() && maxN[q.back()] <= maxN[r])
q.pop_back();
q.push_back(r);
}
r++;
}
] - num[q.front()][] > d + mid)
q.pop_front();
if(!q.empty()){
ALLmax = max(ALLmax , maxN[i] = maxN[q.front()] + num[i][]);
vis[i] = ;
}
;
}
return ALLmax >= K;
}
int main(){
N = read(); d = read(); K = read();
; i <= N ; i++){
num[i][] = read();
num[i][] = read();
}
vis[] = ;
, r = 1e9 + ;
while(l < r){
;
if(check(mid)) r = mid;
;
}
) cout << -;
else cout << l;
;
}
*跳房子
![P1941 [NOIP2014 提高组] 飞扬的小鸟 题解](https://www.kunjuke.com/file/css/thumb/7.jpg/280-180.jpg)
![P1880 [NOI1995] 石子合并 题解](https://www.kunjuke.com/file/css/thumb/9.jpg/280-180.jpg)
![P5020 [NOIP2018 提高组] 货币系统 题解](https://www.kunjuke.com/file/css/thumb/3.jpg/280-180.jpg)
