Crazy Binary String
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
ZYB loves binary strings (strings that only contains `0' and `1'). And he loves equal binary strings\textit{equal binary strings}equal binary strings more, where the number of `0' and the number of `1' in the string are equal.
ZYB wants to choose a substring from an original string T\ T T so that it is an equal binary string\textit{equal binary string}equal binary string with the longest length possible. He also wants to choose a subsequence of T\ T T which meets the same requirements.
A string v\ v v is a substring of a string w\ w w if v\ v v is empty, or there are two integers l\ l l and r (1≤l≤r≤∣w∣)r \ (1 \le l \le r \le |w|)r (1≤l≤r≤∣w∣) such that v=wlwl+1⋯wrv=w_lw_{l+1}\cdots w_rv=wlwl+1⋯wr. A string v\ v v is a subsequence of a string w\ w w if it can be derived from w\ w w by deleting any number (including zero) of characters without changing the order of the remaining characters.
For simplicity, you only need to output the maximum possible length. Note that the empty string is both a substring and a subsequence of any string.
输入描述:
The first line of the input contains a single integer N (1≤N≤100000)N \ (1 \le N \leq 100000)N (1≤N≤100000), the length of the original string T\ T T. The second line contains a binary string with exactly N\ N N characters, the original string T\ T T.
输出描述:
Print two integers A\ A A and B\ B B, denoting the answer for substring and subsequence respectively.
示例1
输入
8 01001001
输出
4 6
子序列显然可以取满，子串数量用dp去维护，签到题
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
int n,dp[2][maxn];
char s[maxn];
bool check(int len){
rep(i,1,n){
if(i+len-1>n) break;
if(dp[0][i+len-1]-dp[0][i-1]==dp[1][i+len-1]-dp[1][i-1]) return 1;
}
return 0;
}
void solve(){
rep(i,0,n) dp[0][i]=dp[1][i]=0;
int ans1=0,ans2=0;
rep(i,1,n){
dp[0][i]=dp[0][i-1]+(s[i]=='0');
dp[1][i]=dp[1][i-1]+(s[i]=='1');
}
ans2=min(dp[0][n],dp[1][n]);
int l=0,r=2*n,mid;
while(l<=r){
mid=(l+r)>>1;
if(mid%2) mid++;
if(check(mid)) l=mid+2,ans1=mid;
else r=mid-2;
}
printf("%d %d\n",ans1,ans2*2);
}
int main() {
while(~scanf("%d%s",&n,s+1)) solve();
}
Big Integer
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
For little pupils, a very large number usually means an integer with many many digits. Let's define a class of big integers which consists only of the digit one (11⋯1)(11 \cdots 1)(11⋯1). The first few integers in this class are 1,11,111,1111⋯1, 11, 111, 1111 \cdots1,11,111,1111⋯. Denote A(n)\ A(n) A(n) as the n\ n n-th smallest integer in this class. To make it even larger, we consider integers in the form of A(ab)A(a^b)A(ab). Now, given a prime number p\ p p, how many pairs (i,j)\ (i, j) (i,j) are there such that 1≤i≤n, 1≤j≤m, A(ij)≡0(mod p)1 \leq i \leq n,\ 1 \leq j \leq m,\ A(i^j) \equiv 0(mod \ p)1≤i≤n, 1≤j≤m, A(ij)≡0(mod p).
输入描述:
The input contains multiple cases. The first line of the input contains a single integer T (1≤T≤100)T \ (1 \le T \le 100)T (1≤T≤100), the number of cases.
For each case, the input consists of a single line, which contains 3 positive integers p,n,m (p,n,m≤109)p, n, m \ (p, n, m \leq 10^9)p,n,m (p,n,m≤109).
输出描述:
Print the answer, a single integer, in one separate line for each case.
示例1
输入
2 11 8 1 7 6 2
输出
4 2
数论题，队友秒的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,p,a[110],b[110],r,cnt;
void calc(ll x){
cnt=0;
for(int i=2;i*i<=x;i++){
if(x%i==0){
++cnt;
a[cnt]=i;
b[cnt]=0;
while(x%i==0) x/=i,b[cnt]++;
}
}
if(x){
cnt++;
a[cnt]=x;
b[cnt]=1;
}
return;
}
ll qp(ll a,ll b,ll md){
ll ret=1;
while(b){
if(b&1) ret=(ret*a)%md;
a=a*a%md;
b>>=1;
}
return ret;
}
ll solve(ll n,ll m,ll r){
calc(r);
ll ret=0;
ll ma=-1;
for(int i=1;i<=cnt;i++) ma=max(ma,b[i]);
for(int j=1;j<=min(ma,m);j++){
ll tmp=1;
for(int i=1;i<=cnt;i++){
ll bs=(b[i]+j-1)/j;
for(int k=1;k<=bs;k++) tmp*=a[i];
}
ret+=n/tmp;
}
if(m>ma){
ll bs=1;
for(int i=1;i<=cnt;i++) bs*=a[i];
ret+=(n/bs)*(m-ma);
}
return ret;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%lld%lld%lld",&p,&n,&m);
if(p==2 || p==5){
printf("0\n");
continue;
}
if(p==3){
r=3;
}
else{
r=p-1;
calc(r);
for(int i=1;i<=cnt;i++){
for(int j=1;j<=b[i];j++){
if(qp(10%p,r/a[i],p)==1){
r/=a[i];
}
else{
break;
}
}
}
}
printf("%lld\n",solve(n,m,r));
}
return 0;
}
Planting Trees
时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
The semester is finally over and the summer holiday is coming. However, as part of your university's graduation requirement, you have to take part in some social service during the holiday. Eventually, you decided to join a volunteer group which will plant trees in a mountain.
To simplify the problem, let's represent the mountain where trees are to be planted with an N×NN \times NN×N grid. Let's number the rows 1\ 1 1 to N\ N N from top to bottom, and number the columns 1\ 1 1 to N\ N N from left to right. The elevation of the cell in the i\ i i-th row and j\ j j-th column is denoted by ai,ja_{i,j}ai,j. Your leader decides that trees should be planted in a rectangular area within the mountain and that the maximum difference in elevation among the cells in that rectangle should not exceed M. In other words, if the coordinates of the top-left and the bottom-right corners of the rectangle are (x1,y1)(x_1,y_1)(x1,y1) and (x2,y2)(x_2,y_2)(x2,y2), then the condition ∣ai,j−ak,l∣≤M|a_{i,j} - a_{k,l}| \le M∣ai,j−ak,l∣≤M must hold for x1≤i,k≤x2, y1≤j,l≤y2x_1 \le i,k \le x_2, \ y_1 \le j,l \le y_2x1≤i,k≤x2, y1≤j,l≤y2. Please help your leader calculate the maximum possible number of cells in such a rectangle so that he'll know how many trees will be planted.
输入描述:
The input contains multiple cases. The first line of the input contains a single integer T (1≤T≤1000)T \ (1 \le T \le 1000)T (1≤T≤1000), the number of cases.
For each case, the first line of the input contains two integers N (1≤N≤500)N\ (1 \le N \le 500)N (1≤N≤500) and M (0≤M≤105)M\ (0 \le M \le 10^5)M (0≤M≤105). The following N lines each contain N integers, where the j\ j j-th integer in the i\ i i-th line denotes ai,j (1≤ai,j≤105)a_{i,j} \ (1 \le a_{i,j} \le 10^5)ai,j (1≤ai,j≤105).
It is guaranteed that the sum of N3N^3N3 over all cases does not exceed 25⋅10725 \cdot 10^725⋅107.
输出描述:
For each case, print a single integer, the maximum number of cells in a valid rectangle.
示例1
输入
2 2 0 1 2 2 1 3 1 1 3 2 2 3 1 3 2 1
输出
1 4
枚举子矩阵上下边界，单调栈+尺取法，复杂度o(n^3)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
int n,m,a[550][550];
int maxx[maxn],minx[maxn];
inline int read(){
int x = 0;
char c = getchar();
bool flag = 0;
while(!isdigit(c)) {
if(c == '-')
flag = 1;
c = getchar();
}
while(isdigit(c)) {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return flag ? -x : x;
}
inline void write(ll x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
struct Stack{
int L,R,val[550],id[550];
void clear(){L=1,R=0;}
void insert(int x,int i){
while(L<=R&&x>=val[R]) R--;
val[++R]=x;
id[R]=i;
}
void erase(int i){if(L<=R&&id[L]==i) L++;}
int top(){return val[L];}
}st1,st2;
void solve(){
n=read();m=read();
int ans=0;
rep(i,1,n) rep(j,1,n) scanf("%d",&a[i][j]);
rep(i,1,n){
rep(t,1,n) maxx[t]=0,minx[t]=maxn;
rep(j,i,n){
st1.clear();st2.clear();
rep(t,1,n) maxx[t]=max(maxx[t],a[j][t]),minx[t]=min(minx[t],a[j][t]);
int start=1;
rep(t,1,n){
st1.insert(maxx[t],t);
st2.insert(-minx[t],t);
while(start<=t&&st1.top()+st2.top()>m){
st1.erase(start);
st2.erase(start);
start++;
}
if(start<=t) ans=max(ans,(t-start+1)*(j-i+1));
}
}
}
write(ans);puts("");
}
int main(){
int T;T=read();
while(T--) solve();
}
Removing Stones
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Summer vacation is coming and Mark has returned home from his university having successfully survived the exam week. Today, he is very bored. So his friend Alice challenges him to play a game with stones which is invented by her. Alice gives Mark N\ N N piles of stones numbered from 1\ 1 1 to N\ N N, and there are aia_iai stones in the i\ i i-th pile. The rules of the game are simple: Mark will try to remove all stones. In each move, Mark chooses two different non-empty piles and removes one stone from each of those two piles. Mark can perform any number of moves. If all the piles are empty after some number of moves, Mark wins the game. If he can't make a valid move but not all piles are empty, he loses the game. Obviously, if the total number of stones is odd, then Mark is not able to win the game. So there is an additional rule: if initially, the total number of stones is odd, then Mark removes a single stone from the pile with the fewest stones before starting the game. If there are multiple piles with the smallest number of stones, Mark chooses one among them to remove a stone.
Mark found the optimal strategy for Alice's game very quickly and gets bored again. Also, he noticed that for some configuration of stones there is no way to win. So he challenges you to solve this problem: count the number of integer pairs (l,r) (1≤l<r≤N)(l,r) \ (1 \le l < r \le N)(l,r) (1≤l<r≤N) such that it is possible for Mark to win the game if the game is played using only the piles numbered from l\ l l to r\ r r.
输入描述:
The input contains multiple cases. The first line of the input contains a single positive integer T\ T T, the number of cases.
The first line of each case contains a single integer N (2≤N≤300000)N \ (2 \le N \le 300000)N (2≤N≤300000), the number of piles. The following line contains N\ N N space-separated integers, where the i\ i i-th integer denotes ai (1≤ai≤109)a_i \ (1 \le a_i \le 10^9)ai (1≤ai≤109), the number of stones in the i\ i i-th pile.
It is guaranteed that the sum of N\ N N over all cases does not exceed 1000000\ 1000000 1000000.
输出描述:
For each case, print a single integer on a single line, the number of pairs satisfying the required property.
示例1
输入
2 3 1 1 1 4 1 2 3 4
输出
3 3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[300100];
ll pre[300100];
int st[300100][25];
ll cnt;
void init(int n){
for(int i=1;i<=n;i++){
st[i][0]=i;
}
for(int j=1;(1<<j)<=n+1;j++){
for(int i=1;i+(1<<j)<=n+1;i++){
if(a[st[i][j-1]]>a[st[i+(1<<(j-1))][j-1]]){
st[i][j]=st[i][j-1];
}
else{
st[i][j]=st[i+(1<<(j-1))][j-1];
}
}
}
return;
}
int que(int l,int r){
int k=(int)(log((double)(r-l+1))/log(2.0));
if(a[st[l][k]]>a[st[r-(1<<k)+1][k]]){
return st[l][k];
}
else{
return st[r-(1<<k)+1][k];
}
}
void gao(int l,int r){
if(l>=r) return;
int k;
k=que(l,r);
int ma=a[k];
int llen=k-l,rlen=r-k;
if(llen<=rlen){
for(int i=l;i<=k;i++){
int ub=r,lb=k;
int ans=-1;
while(ub>=lb){
int md=(ub+lb)>>1;
if(pre[md]-pre[i-1]>=2*ma){
ans=md;
ub=md-1;
}
else{
lb=md+1;
}
}
if(ans!=-1){
cnt+=1ll*(r-ans+1);
}
}
}
else{
for(int i=k;i<=r;i++){
int ub=k,lb=l;
int ans=-1;
while(ub>=lb){
int md=(ub+lb)>>1;
if(pre[i]-pre[md-1]>=2*ma){
ans=md;
lb=md+1;
}
else{
ub=md-1;
}
}
if(ans!=-1){
cnt+=1ll*(ans-l+1);
}
}
}
gao(l,k-1);
gao(k+1,r);
return;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
init(n);
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+1ll*a[i];
}
cnt=0;
gao(1,n);
printf("%lld\n",cnt);
}
return 0;
}
Magic Line
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
There are always some problems that seem simple but is difficult to solve.
ZYB got N\ N N distinct points on a two-dimensional plane. He wants to draw a magic line so that the points will be divided into two parts, and the number of points in each part is the same. There is also a restriction: this line can not pass through any of the points.
Help him draw this magic line.
输入描述:
There are multiple cases. The first line of the input contains a single integer T (1≤T≤10000)T \ (1 \leq T \leq 10000)T (1≤T≤10000), indicating the number of cases.
For each case, the first line of the input contains a single even integer N (2≤N≤1000)N \ (2 \leq N \leq 1000)N (2≤N≤1000), the number of points. The following $N$ lines each contains two integers xi,yi (∣xi,yi∣≤1000)x_i, y_i \ (|x_i, y_i| \leq 1000)xi,yi (∣xi,yi∣≤1000), denoting the x-coordinate and the y-coordinate of the i\ i i-th point.
It is guaranteed that the sum of N\ N N over all cases does not exceed 2×1052 \times 10^52×105.
输出描述:
For each case, print four integers x1,y1,x2,y2x_1, y_1, x_2, y_2x1,y1,x2,y2 in a line, representing a line passing through (x1,y1)(x_1, y_1)(x1,y1) and (x2,y2)(x_2, y_2)(x2,y2). Obviously the output must satisfy (x1,y1)≠(x2,y2)(x_1,y_1) \ne (x_2,y_2)(x1,y1)=(x2,y2).
The absolute value of each coordinate must not exceed 10910^9109. It is guaranteed that at least one solution exists. If there are multiple solutions, print any of them.
示例1
输入
1 4 0 1 -1 0 1 0 0 -1
输出
-1 999000000 1 -999000001
乱搞，反正答案范围很大
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
ll x,y;
node operator + (const node& b) const {
return (node){x+b.x,y+b.y};
}
node operator - (const node& b) const {
return (node){x-b.x,y-b.y};
}
ll operator * (const node& b) const {
return x*b.y-y*b.x;
}
node operator *(const ll& b)const{
return (node){x*b,y*b};
}
ll len() const {
return x*x+y*y;
}
};
int cmp1(const node& a,const node& b) {
return (a.y<b.y||((a.y==b.y) && (a.x<b.x)));
}
int cmp2(const node& a,const node& b){
return a*b>0 || (a*b==0 && a.len()<b.len());
}
node a[1500];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&a[i].x,&a[i].y);
}
node bs;
bs.x=-2001,bs.y=-60000;
for(int i=1;i<=n;i++){
a[i]=a[i]-bs;
}
sort(a+1,a+1+n,cmp2);
node x=a[n/2],y=a[n/2+1];
node xx=x*2+bs,yy=y*2+bs;
node res;
res.x=(xx.x+yy.x)/2,res.y=(xx.y+yy.y)/2;
printf("%lld %lld %lld %lld\n",bs.x,bs.y,res.x,res.y);
}
return 0;
}
LRU management
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
ZYB has finished his computer course recently. He is very interested in the LRU algorithm for cache management.
To simplify the problem, assume that a block contains a name (which is a string) and a set of data (which is a number). ZYB wants to implement the LRU algorithm with an array.
His array can hold at most M\ M M elements at any time. In the beginning, the array is empty. In each operation, the CPU may access a block s\ s s. ZYB will search for it in his array by brute force. If this block is present in his array (which means he can find a block with the same name), he takes it out of the array and puts it back at the end of the array. Otherwise, he simply adds it to the end of the array. If at any time, the size of the array exceeds the capacity, he will remove the first block in his array (the block at the front of the array).
Seems boring? Well, sometimes ZYB may ask the data of a block in, before or after a certain block. Could you help him to write a program to achieve his goal?
输入描述:
There are multiple cases. The first line of the input contains a single positive integer T\ T T, indicating the number of cases.
For each case, the first line of the input contains two integers Q\ Q Q and M (1≤Q, M≤500000)M\ (1 \leq Q, \ M \leq 500000)M (1≤Q, M≤500000), denoting the number of operations and the capacity of the array. The following Q\ Q Q lines each contain an integer opt (0≤opt≤1)opt \ (0 \le opt \le 1)opt (0≤opt≤1), a string s (1≤∣s∣≤10)s \ (1 \leq |s| \leq 10)s (1≤∣s∣≤10) and an integer v\ v v, separated by single spaces, describing an operation.
If opt=0\ opt = 0 opt=0, then ∣v∣<10\ |v| < 10 ∣v∣<10, and the operation is that the CPU wants to access a block. If this access misses (which means you can't find a block in the array with the name s\ s s), add a block at the end of the array with the name s\ s s and the data v\ v v, and the result of the operation is v\ v v. If this access hits, the result of the operation is the data of the block you found (ignore v\ v v in this case). Don't forget to move that block to the end of the array.
If opt=1\ opt = 1 opt=1, then v\ v v will be −1,0\ -1,0 −1,0 or 1\ 1 1 , and the operation is that you should answer ZYB's question. Let k\ k k be the index of the block with the name s\ s s in the array. Then the result of this operation is the data of the block with the index k+v\ k+v k+v in the array. If such block doesn't exist, please output ``Invalid'' (without quotation marks) instead.
Note that ZYB's questions (operations of type 1\ 1 1) don't count as access and don't cause the array to be updated.
It is guaranteed that the sum of Q\ Q Q over all cases does not exceed 1000000\ 1000000 1000000, and that s\ s s only contains digits (i.e. `0' - `9').
输出描述:
For each case, print the result of each operation in a line as defined in the input section of the statement.
示例1
输入
1 8 3 0 0101010 1 0 0101011 2 1 0101010 1 0 1100000 3 0 0101011 -1 0 1111111 4 1 0101011 -1 1 0101010 0
输出
1 2 2 3 2 4 3 Invalid
复杂大模拟，过程不说了模拟就对了
#include <bits/stdc++.h>
using namespace std;
struct node{
int pre,nxt;
int v;
};
node p[500100];int cnt=1,len=0;
bool mk[500100];
struct nd{
int pt[10];
int val;
void init(){
memset(pt,-1,sizeof(pt));
val=-1;
return;
}
};
void add_node(int ed,int val){
p[cnt].nxt=p[ed].nxt;
p[cnt].v=val;
p[cnt].pre=ed;
mk[cnt]=1;
p[ed].nxt=cnt;
p[p[cnt].nxt].pre=cnt;
cnt++;
return;
}
void del(int pt){
p[p[pt].pre].nxt=p[pt].nxt;
p[p[pt].nxt].pre=p[pt].pre;
mk[pt]=0;
return;
}
struct tr{
nd trie[5000100];int num;
void init(){
trie[1].init();
num=2;
return;
}
int que(char s[],int pt,int pos,int l){
if(pt==l) return trie[pos].val;
int tar=s[pt]-'0';
if(trie[pos].pt[tar]!=-1){
return que(s,pt+1,trie[pos].pt[tar],l);
}
return -1;
}
void ins(char s[],int pt,int pos,int l,int cnt){
if(pt==l){
trie[pos].val=cnt;
return;
}
int tar=s[pt]-'0';
if(trie[pos].pt[tar]!=-1){
ins(s,pt+1,trie[pos].pt[tar],l,cnt);
}
else{
trie[num].init();
trie[pos].pt[tar]=num;
num++;
ins(s,pt+1,trie[pos].pt[tar],l,cnt);
}
return;
}
};
tr trie;
int main(){
int T;
scanf("%d",&T);
while(T--){
len=0;
cnt=1;
trie.init();
memset(mk,0,sizeof(mk));
p[cnt++]=(node){-1,-1,-1};
add_node(1,-1);
int ed=1;
char s[50];
int n,m;
scanf("%d%d",&n,&m);
while(n--){
int typ,v;
scanf("%d%s%d",&typ,s,&v);
if(typ==0){
int fg=trie.que(s,0,1,strlen(s));
if(fg!=-1 && mk[fg]==0) fg=-1;
if(fg!=-1){
printf("%d\n",p[fg].v);
add_node(ed,p[fg].v);
ed=cnt-1;
trie.ins(s,0,1,strlen(s),ed);
del(fg);
}
else{
printf("%d\n",v);
add_node(ed,v);
trie.ins(s,0,1,strlen(s),cnt-1);
ed=cnt-1;
len++;
if(len>m){
len--;
del(p[1].nxt);
}
}
}
else{
int fg=trie.que(s,0,1,strlen(s));
if(fg!=-1 && mk[fg]==0) fg=-1;
if(fg!=-1){
if(v==1) fg=p[fg].nxt;
if(v==-1) fg=p[fg].pre;
}
if(fg==-1 || fg==1 || fg==2){
printf("Invalid\n");
}
else{
printf("%d\n",p[fg].v);
}
}
}
}
return 0;
}
