练习赛9

practise

A hesorchen

//https://blog.csdn.net/hesorchen
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <list>
#include <set>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
#define ll long long
#define lowbit (a & (-a))
#define endl "\n"
#define PI acos(-1.0)
#define mod 1000000009
#define INF 0x3f3f3f3f
#define MAX 200010
int main()
{
    ll a, b;
    cin >> a >> b;
    cout << a * a - b << endl;
    return 0;
}

B 1292224662

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
struct point{
    db x,y;
    point(){};
    point(db _x,db _y):x(_x),y(_y){}
    db len2(){
        return x*x+y*y;
    }
    point operator +(const point& b)const{
        return point(x+b.x,y+b.y);
    }
    point operator -(const point& b)const{
        return point(x-b.x,y-b.y);
    }
    point operator *(const db& k)const{
        return point(k*x,k*y);
    }
    point operator /(const db& k)const{
        return point(x/k,y/k);
    }
    db operator *(const point& b)const{
        return x*b.x+y*b.y;
    }
};
struct line{
    point s,e;
    line(){};
    point lineprog(point p){
        return s+( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) ); 
    }
};
int q;
db sx,sy,ex,ey,qx,qy;
int main(){
    cin>>sx>>sy>>ex>>ey;
    cin>>q;
    line l;
    l.s={sx,sy};
    l.e={ex,ey};
    while(q--){
        cin>>qx>>qy;
        point ans=l.lineprog({qx,qy});
        printf("%.10f %.10f\n",ans.x,ans.y);
    }
    return 0;
}

C hesorchen

//https://blog.csdn.net/hesorchen
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <list>
#include <set>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
#define ll long long
#define lowbit (a & (-a))
#define endl "\n"
#define PI acos(-1.0)
#define mod 1000000009
#define INF 0x3f3f3f3f
#define MAX 200010
ll p[100];
int main()
{
    p[1] = 1;
    p[2] = 2;
    for (int i = 3; i <= 50; i++)
        p[i] = p[i - 1] + p[i - 2];
    int t;
    cin >> t;
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        // ll a = 1;
        // ll b = 2;
        ll temp = m - n;
        cout << p[temp] << endl;
    }
    return 0;
}

D 1292224662

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
char s[60];
bool legal(int l,int r){
    int bra=0;
    for(int i=l;i<=r;i++){
        if(s[i]=='('){
            bra++;
        }
        else{
            if(bra) bra--;
            else    return false;
        }
    }
    if(bra) return false;
    else    return true;
}
int get(int l,int r){
    if(r-l+1==2){
        return 1;
    }
    if(legal(l+1,r-1)){
        return 2*get(l+1,r-1);
    }
    for(int i=l+1;i<=r-1;i++){
        if(legal(l,i)&&legal(i+1,r)){
            return get(l,i)+get(i+1,r);
        }
    }
    assert(0);
}
int main(){
    cin>>(s+1);
    cout<<get(1,strlen(s+1))<<endl;
    return 0;
}

E 1292224662

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
char s[1010];
int ans[1010];
int main(){
    cin>>(s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++){
        if(s[i]=='a'){
            while(s[i]=='a')    i++;
            i--;
            ans[i]=1;
        }
        else{
            while(s[i]=='b')    i++;
            i--;
            if(i!=n)    ans[i]=1;
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d%c",ans[i],(i==n)?'\n':' ');
    }
    return 0;
}

F 1292224662

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
char s[310],s1[310],s2[310],ans[310];
int dp[310][310];
int p;
void work(int n1,int n2){
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n1;i++){
        for(int j=1;j<=n2;j++){
            if(s1[i]==s2[j]){
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
            }
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
            dp[i][j]=max(dp[i][j],dp[i][j-1]);
        }
    }
}
void get(int i,int j){
    if(i==0||j==0){
        return ;
    }
    if(dp[i][j]==dp[i-1][j]){
        get(i-1,j);
    }
    else if(dp[i][j]==dp[i][j-1]){
        get(i,j-1);
    }
    else if(dp[i][j]==dp[i-1][j-1]+1){
        assert(s1[i]==s2[j]);
        ans[++p]=s[i];
        get(i-1,j-1);
    }
}
int main(){
    while(1){
        scanf("%s",s+1);
        if(s[1]=='#')   break;
        int n=strlen(s+1);
        p=0;
        for(int i=1;i<n;i++){
            memset(s1,0,sizeof(s1));
            memset(s2,0,sizeof(s2));
            for(int j=1;j<=i;j++)   s1[j]=s[j];
            for(int j=i+1;j<=n;j++) s2[j-i]=s[j];
            int n1=strlen(s1+1);
            int n2=strlen(s2+1);
            work(n1,n2);
            if(dp[n1][n2]>p){
                p=0;
                get(n1,n2);
            }
        }
        for(int i=p;i>=1;i--){
            putchar(ans[i]);
        }putchar('\n');
    }
    return 0;
}

G 1292224662

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
char s[200010];
int kmp[200010],n,t;
void mkkmp(){
    int j=0;
    for(int i=2;i<=n;i++){
        while(j&&s[j+1]!=s[i])
            j=kmp[j];
        if(s[j+1]==s[i])
            j++;
        kmp[i]=j;
    }
    return ;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        scanf("%s",s+1);
        memset(kmp,0,sizeof(kmp));
        mkkmp();
        int ans=n;
        for(int i=2;i<=n;i++){
            int sv=i;
            while(kmp[sv]){
                ans++;
                sv=kmp[sv];
            }
        }
        printf("%d\n",ans%10007);
    }
    return 0;
}

H 1292224662

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int t,n,a[100010],p;
char s[40];
struct dic_tree{
    int tot;
    int nxt[3200010][2];
    void clear(){
        for(int i=0;i<=tot+5;i++){
            nxt[i][0]=nxt[i][1]=0;
        }tot=0;
    }
    void insert(char* s){
        int now=0;
        for(int i=1;i<=32;i++){
            if(nxt[now][s[i]-'0']){
                now=nxt[now][s[i]-'0'];
            }
            else{
                nxt[now][s[i]-'0']=++tot;
                now=tot;
            }
        }
    }
    int query(char* s){
        int now=0,ans=0;
        for(int i=1;i<=32;i++){
            if(nxt[now][1-(s[i]-'0')]){
                ans=ans*2+1;
                now=nxt[now][1-(s[i]-'0')];
            }
            else{
                ans=ans*2;
                now=nxt[now][s[i]-'0'];
            }
        }
        return ans;
    }
}tree;
void itos(int x){
    for(int i=1;i<=32;i++){
        s[i]=(x&1)+'0';
        x>>=1;
    }
    for(int i=1;i<=16;i++){
        swap(s[i],s[33-i]);
    }
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
            itos(a[i]);
            tree.insert(s);
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            itos(a[i]);
            ans=max(ans,tree.query(s));
        }
        printf("%d\n",ans);
        tree.clear();
    }
    return 0;
}

I 1292224662

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
int n,mod=1000000009;
int a[110][110];
int dis[110][110],vis[110][110],way[110][110];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool ok(pii pos){
    int xx=pos.first,yy=pos.second;
    if(xx<1||yy<1||xx>n||yy>n)
        return false;
    if(xx+yy>=n+1)
        return false;
    return true;
}
int main(){
    while(1){
        cin>>n;
        if(!n)  break;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j+i<n+1;j++){
                a[i][j]+=a[n+1-j][n+1-i];
            }
        }
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        memset(way,0,sizeof(way));
        queue<pii> q;
        q.push({1,1});vis[1][1]=1;
        dis[1][1]=0;
        while(!q.empty()){
            pii now=q.front();q.pop();
            vis[now.first][now.second]=0;
            for(int i=0;i<4;i++){
                pii to={now.first+dx[i],now.second+dy[i]};
                if(dis[to.first][to.second]>dis[now.first][now.second]+a[to.first][to.second]){
                    dis[to.first][to.second]=dis[now.first][now.second]+a[to.first][to.second];
                    if(ok(to)&&vis[to.first][to.second]==0){
                        vis[to.first][to.second]=1;
                        q.push({to.first,to.second});
                    }
                }
            }
        }
        int mn=1e9;
        for(int i=1;i<=n;i++){
            mn=min(dis[i][n+1-i],mn);
        }
        for(int i=1;i<=n;i++){
            if(dis[i][n+1-i]==mn){
                q.push({i,n+1-i});
                way[i][n+1-i]=1;
                vis[i][n+1-i]=1;
            }
        }
        while(!q.empty()){
            pii now=q.front();q.pop();
            for(int i=0;i<4;i++){
                pii to={now.first+dx[i],now.second+dy[i]};
                if(dis[to.first][to.second]+a[now.first][now.second]==dis[now.first][now.second]){
                    way[to.first][to.second]+=way[now.first][now.second];
                    way[to.first][to.second]%=mod;
                    if(ok(to)&&vis[to.first][to.second]==0){
                        q.push({to.first,to.second});
                        vis[to.first][to.second]=1;
                    }
                }
            }
        }
        printf("%d\n",way[1][1]%mod);
    }
    return 0;
}

J puluo

#include<stack>
#include<iostream>
using namespace std;
int pre[1000006],maxer[1000006];
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int n,m,p,tmp;
    char c;
    stack<int>left,right;
    while(scanf("%d",&n)!=EOF)
    {
        while(!left.empty())left.pop();
        while(!right.empty())right.pop();
        for(int i=0;i<=n+1;i++)maxer[i]=-999999999;
        p=0;
        while(n--)
        {
            getchar();
            scanf("%c",&c);
            if(c=='I')
            {
                scanf("%d",&m);
                left.push(m);
                p++;
                if(p>1)pre[p]=pre[p-1]+m;
                else pre[p]=m;
                maxer[p]=max(maxer[p-1],pre[p]);
            }
            if(c=='D'&&!left.empty())
            {
                left.pop();
                p--;
            }
            if(c=='L'&&!left.empty())
            {
                tmp=left.top();
                right.push(tmp);
                left.pop();
                p--;
                /*pre[p]=pre[p-1]+tmp;
                maxer[p]=max(maxer[p-1],pre[p]);*/
            }
            if(c=='R'&&!right.empty())
            {
                tmp=right.top();
                right.pop();
                left.push(tmp);
                p++;
                pre[p]=pre[p-1]+tmp;
                maxer[p]=max(maxer[p-1],pre[p]);
            }
            if(c=='Q')
            {
                scanf("%d",&m);
                printf("%d\n",maxer[m]);
            }
        }
    }
}