牛客，第二十届北京师范大学程序设计竞赛，签到题7题

序

题号 标题 已通过代码 通过率 团队的状态
A 小凯的疑惑 点击查看 434/745 通过
B 幻象踩花 点击查看 121/434 通过
C 跳刀抓人 点击查看 26/178 通过
D 真正的卡尔 点击查看 115/714 通过
E 刷新的艺术 点击查看 31/479 通过
F 最后的战役 点击查看 1/39 未通过
G 随机数生成器 点击查看 1/20 未通过
H 字符串 点击查看 25/130 通过
I 修罗牌浪 点击查看 1/4 未通过
J 集合论 点击查看 72/242 通过
K 有趣的矩阵 点击查看 6/20 未通过

A、小凯的疑惑

• NOIP2017D1T1原题，小学奥数公式，结论是ab-a-b。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL ksm(LL a, LL b){if(b==0)return 1;LL ns=ksm(a,b>>1);ns=ns*ns%mod;if(b&1)ns=ns*a%mod;return ns;}
void EXGCD(int a, int b, int &d, int &x,  int & y, int MOD) { if (b==0) { d = a; x = 1; y = 0; } else { EXGCD(b, a % b, d, y, x, MOD); y -= x * (a / b); } }
int inv(int a, int MOD) { int d=0, x=0, y=0; EXGCD(a, MOD,  d,  x, y, MOD); return d == 1 ? (x + MOD) % MOD : -1; }
int main(){
    LL a, b;  cin>>a>>b;
    cout<<a*b-a-b;
    return 0;
}


  

B、幻象踩花

• 画图以后结论题，注意特判
• 开始思路错了几个方向，后来特判想了好一会儿，

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi = acos(-1);

int main(){
    //cout<<area(point{2,0},1, point{-2,-2},2.8)<<"\n";
    int T;  cin>>T;
    while(T--){
        LL R, r, x, y;  cin>>R>>r>>x>>y;
        if(x*x+y*y>(R+r)*(R+r) || x*x+y*y<=(R-r)*(R-r)){
            printf("%.10lf\n",0 );  continue;
        }
        double d = sqrt(x*x+y*y);
        double t = (x*x+y*y+R*R-r*r)*1.0/(2*d*R);
        //cout<<t<<"\n";
        double ans = acos(t)/pi*2;
        printf("%.10lf\n",ans );
    }
    return 0;
}


  

C、跳刀抓人

• 暴力bfs，对于闪烁操作，在每个节点中多维护一个time表示当前是第几秒，转移时特判当前能否转移。
• 没有判断能否转移，直接全部暴力转移了，WA了好久

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi = acos(-1);
struct node{int x, y, t, time;};
struct cmp{
	bool operator()(node a, node b){ return a.t > b.t; }
};
priority_queue<node, vector<node>, cmp>q;

int xx[] = {0,0,-1,1};
int yy[] = {1,-1,0,0};

char a[110][110];
int vis[110][110][10];
int main(){
    int n, m;  cin>>n>>m;
    node st, ed;
    for(int i = 1; i <= n; i++){
        //scanf("%s",a[i]+1);
        for(int j = 1; j <= m; j++){
            cin>>a[i][j];
            if(a[i][j]=='A')st = node{i,j,0,7};
            if(a[i][j]=='B')ed = node{i,j,0,7};
        }
    }
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= m; j++){
    //         cout<<a[i][j];
    //     }
    //     cout<<"\n";
    // }
    //queue<node>q;
    q.push(st);
    while (q.size()){
        node t = q.top();  q.pop();
        t.time = min(t.time, 7);
        if(vis[t.x][t.y][t.time])continue; 
        vis[t.x][t.y][min(t.time,7)] = 1;

        if(a[t.x][t.y]=='B'){
            cout<<t.t<<"\n";
            return 0;
        }
        for(int dx = -3; dx <= 3; dx++){
            for(int dy=-3; dy<=3; dy++){
                if(dx==0&&dy==0)continue;
                int nx=t.x+dx, ny = t.y+dy;
                if(nx<1||nx>n||ny<1||ny>m)continue;
                if(a[nx][ny]=='#')continue;
                if(t.time==7)q.push({nx,ny,t.t+1,0});
                // int nx = t.x+dx, ny = t.y+dy;
                // if(nx<1||nx>n||ny<1||ny>m)continue;
                // if(a[nx][ny]=='#'|| vis[t.x][t.y][nx][ny])continue;
                // int dd = abs(dx)+abs(dy), nt;
                // if(dd==1)nt = 1;else nt=8;
                // if(ok==0){nt=1;}
                // q.push(node{nx,ny,t.t+nt});
                // vis[t.x][t.y][nx][ny] = 1;
            }
        }
        int d = 7-t.time;
        if(t.time<7)q.push({t.x,t.y,t.t+d,7});
        for(int i = 0; i < 4; i++){
            int nx = t.x+xx[i], ny = t.y+yy[i];
            if(nx<1||nx>n||ny<1||ny>m)continue;
            if(a[nx][ny]=='#')continue;
            q.push({nx,ny,t.t + 1,t.time + 1});
        }

    }
    cout<<-1<<'\n';
    return 0;
}





  

D、真正的卡尔

• 排列组合结论题，打表找规律得到递推公式

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 998244353;
const int maxn = 1010;
LL f[maxn][maxn];
int main(){
    for(int i = 1; i <= 1000; i++)f[i][1] = i, f[1][i] = 1;
    for(int i = 2; i <= 1000; i++){
        for(int j = 2; j <= 1000; j++){
            f[i][j] = (f[i-1][j]+f[i][j-1])%mod;
        }
    }
    int T;  cin>>T;
    while(T--){
        int a, b;  cin>>a>>b;
        cout<<f[a][b]<<"\n";
    }
    return 0;
}



  

E、刷新的艺术

• 分类讨论结论题，开始有两种情况没有想到

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi = acos(-1);
int gcd(int a, int b){ return b==0 ? a : gcd(b,a%b); }
void out(int x, int y){
    if(x%y==0)cout<<x/y<<"\n";
    else cout<<x/gcd(x,y)<<"/"<<y/gcd(x,y)<<"\n";
}

int main(){
    int T;  cin>>T;
    while(T--){
        int a, b;  cin>>a>>b;
        if(a>b){
            //cout<<b<<"\n";  continue;
            if(a>b*2)cout<<b<<"\n";else out(a,2);
            continue;
        }

        //out(b, b/a+1);
        if(b%a==0)out(b,b/a+1);
        else{
            int c = b/a+1;
            if(b*1.0/c < a*1.0*c/(c+1))out(b,c);
            else out(a*c,c+1);
        }

    }
    return 0;
}





  

H、字符串

• KMP暴力出所有区间，然后贪心，按照左端点排序扫一遍更新答案
• 扫的时候需要考虑区间右边的重合情况，额外开个队列维护

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7+100;

int n, m, k;  string s,p;
struct node{int l, r;};
bool cmp(node x, node y){
    return x.l<y.l;
}
vector<node>vc;

int nxt[maxn];
void pre_next(string p){
	int j = 0; //j表示到i-1为止的最长前缀的下标
    for(int i = 2; i < p.size(); i++){
		//用到j为止的最长公共前缀的下标，尝试去匹配下一个字母
        while(j && p[i]!=p[j+1])j = nxt[j];
        if(p[i]==p[j+1])j++;
        nxt[i] = j;
    }
}
void kmp(string s, string p){
    int j = 0;
    for(int i = 1; i <= s.size()-1; i++){
		while(j && s[i]!=p[j+1])j = nxt[j];//不停的去找直到s[i]能匹配上下一个
        if(s[i]==p[j+1])j++;//匹配上了就加一
        if(j==p.size()-1){//匹配完了
			int t = i-p.size()+1;
			//cout<<t+1<<" ";
            vc.push_back(node{t+1,t+m});
			j = nxt[j];
		}
    }
}

int main(){
    cin>>n>>m>>k>>s>>p;
	s="0"+s; p="0"+p;
	pre_next(p);
	kmp(s,p);
    sort(vc.begin(),vc.end(),cmp);
    // for(node t : vc){
    //     cout<<t.l<<" "<<t.r<<"\n";
    // }
    queue<int>qu;
    int cnt = 1,  cc = 1;
    qu.push(vc[0].r);
    for(int i = 1; i < vc.size(); i++){
        if(vc[i].l > qu.front()){
            while(vc[i].l > qu.front()&&qu.size()>1){
                qu.pop();
                cc--;
            }
            cnt++;
            cc++;
            qu.push(vc[i].r);
            //cout<<vc[i].l<<" "<<vc[i].r<<" "<<cc<<22<<'\n';

        }else{
            while(cc>=k&&qu.size()>1&&vc[i].l>qu.front()){
                qu.pop();
                cc--;
            }
            if(cc<k){
                cnt++;
                qu.push(vc[i].r);
                cc++;
                //cout<<vc[i].l<<" "<<vc[i].r<<" "<<cc<<'\n';
            }
        }
    }
    cout<<cnt<<"\n";
	return 0;
}


  

J、集合论

• 分四类讨论结论题，二进制函数没开ll卡了很久。

#include<bits/stdc++.h>
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
#define SCC(x) scanf("%d",&x)
#define ISS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
using namespace std;
const int N=1e6+5;
const int D=1e7+5;
const ll MOD=998244353;
const double Pi = acos(-1.0);
//inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
//inline void write(int x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}
//ll pow1(ll a,ll b){ll r=1;while(b){if(b&1)r=r*a;a=a*a;b>>=1;}return r;}
//ll pow2(ll a,ll b,ll mod){ll r=1;while(b){if(b&1)r=r*a%mod;a=a*a%mod;b>>=1;}return r%mod;}
//ll gcd(ll a,ll b){ll m=a%b;while(m){a=b;b=m;m=a%b;}return b;}
//void exgcd(ll a, ll b, ll &d, ll &x, ll &y){if(!b) { d = a; x = 1; y = 0;}else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }}
//ll inv(ll a){ll d, x, y;exgcd(a, MOD, d, x, y);return d == 1 ? (x + MOD) % MOD : -1;}struct node{ll mat[105][105];};node mul(node x,node y,int n,ll mod){node tmp;for(int i=0;i<n;i++)for(int j=0;j<n;j++){tmp.mat[i][j]=0;for(int k=0;k<n;k++)tmp.mat[i][j]+=(x.mat[i][k]*y.mat[k][j])%mod;tmp.mat[i][j]%=mod;}return tmp;}
// node matpow(node x,node y,ll num,int n,ll mod){while(num){if(num&1){y=mul(x,y,n,mod);}x=mul(x,x,n,mod);num=num>>1;}return y;}
//for(int i=2;i<D;i++){if(!np[i]) p[++cnt]=i;for(int j=1;j<=cnt&&p[j]*i<D;j++){np[i*p[j]]=1;if(i%p[j]==0) break;}}
//int find(int x){return a[x]==x?x:a[x]=find(a[x]);}void merge(int x,int y){a[find(y)]=a[find(x)];}
//string s1="0",s2="{0}";
set<ll>t1,t2,t3,t4;
ll highbit(ll x) { return (ll)1 << (63 - __builtin_clzll(x)); }
int main(){
//    cout<<s1<<" "<<s1.size()<<'\n'<<s2<<" "<<s2.size()<<'\n';
//    rep(i,1,10){
//        s1=s1+","+s2;
//        s2="{"+s1+"}";
//        cout<<s2<<" "<<s2.size()<<'\n';
//    }
//    int x;
//    cin>>x;
    ll x,t;
    x=4;rep(i,1,60) t1.insert(x-1),x*=2;
    x=1;rep(i,1,62) t2.insert(x),x*=2;t2.erase(2);
    t3.insert(2);
    x=8;rep(i,1,60) t4.insert(x-2),x*=2;
    cin>>t;
    while(t--){
        cin>>x;
        while(1){
            if(t1.count(x)) {cout<<','<<'\n';break;}
            if(t2.count(x)) {cout<<'{'<<'\n';break;}
            if(t3.count(x)) {cout<<'0'<<'\n';break;}
            if(t4.count(x)) {cout<<'}'<<'\n';break;}

            x=x-highbit(x)+1;

        }
    }
}


  

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/123600446