目录

G Icon Design

题目

​ 打印字符NFL5 (1<=n<=5)

分析

​ 由于n值较小，可以直接打表。也可以模拟绘制,技巧：先用数组存储，利用draw函数可方便绘制。

代码

模拟

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=1e2+5,M=5e5+5;

char str[N][N];
int n;

void draw(int x,int y,int dx,int dy,char ch,int k) {
    for(int i=0;i<k;i++) {
        str[x+dx*i][y+dy*i]=ch;
    }
}

int main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    int T;
    cin>>T;
    while(T--) {
        cin>>n;
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++) {
                if(i==1||i==4*n+5||j==1||j==13*n+19)
                    str[i][j]='@';
                else str[i][j]='.';
            }

        draw(n+2,n+3,1,0,'@',2*n+3);
        draw(n+2,n+3,1,1,'@',2*n+3);
        draw(n+2,3*n+5,1,0,'@',2*n+3);

        draw(n+2,4*n+7,1,0,'@',2*n+3);
        draw(n+2,4*n+7,0,1,'@',2*n+3);
        draw(2*n+3,4*n+7,0,1,'@',2*n+3);

        draw(n+2,7*n+11,1,0,'@',2*n+3);
        draw(3*n+4,7*n+11,0,1,'@',2*n+3);

        draw(n+2,10*n+15,0,1,'@',2*n+3);
        draw(n+2,10*n+15,1,0,'@',n+2);
        draw(2*n+3,10*n+15,0,1,'@',2*n+3);
        draw(2*n+3,12*n+17,1,0,'@',n+2);
        draw(3*n+4,10*n+15,0,1,'@',2*n+3);

        for(int i=1;i<=4*n+5;i++) {
            for(int j=1;j<=13*n+19;j++) {
                cout<<str[i][j];
            }
            cout<<"\n";
        }
    }
	return 0;
}

J  Number Game

题目

​ 存在三个整数A、B、C，两种操作。

​ 1、B -> A-B 2、C->B-C

分析

​ B存在B与A-B两种情况，即为B1和B2。由分析可知，C要轮流减去B1和B2，否则会重复。列式子，并化简。当B1=B2时要特判。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=4e4+10,M=5e5+5;

int n,m,k;
ll a,b,c,x;

int main(){
    //freopen("data.in","r",stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T; cin>>T;
	while(T--) {
        cin>>a>>b>>c>>x;
        ll b1=b,b2=a-b;
        ll t=abs(b1-b2);
        if(b1==b2) {
            if(c==x||b-c==x) {
                cout<<"Yes\n";
            } else {
                cout<<"No\n";
            }
            continue;
        }
        if((x-c)%t==0) {
            cout<<"Yes\n"; continue;
        }
        if((x-(b2-c))%t==0) {
            cout<<"Yes\n"; continue;
        }
        if((x-(b1-c))%t==0) {
            cout<<"Yes\n"; continue;
        }
        cout<<"No\n";
	}
	return 0;
}

B Eezie and Pie

题目

​ 有一棵树，每个节点对其k级以内父节点有影响，求每个节点被影响的数量。

分析

​ 树形差分。及一段简单路径上的节点值都加一，只用让两边端点加一，减一。关键是求得某一节点的k级父节点，可以用用栈来维护。也可以利用LCA中的倍增法求。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10,M=1e6+5;

int n,m,k;
int h[N],ne[N<<1],ver[N<<1],tot=0;
int dep[N],fa[N][22]; //fa[i][k]表示节点i的上2^k层的祖先是哪个点
int ans[N];


void add(int x,int y) {
    ver[++tot]=y; ne[tot]=h[x]; h[x]=tot;
}

void dfs(int x,int pre) {
    dep[x]=dep[pre]+1;
    fa[x][0]=pre;
    for(int i=1;i<=21;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=h[x];i;i=ne[i]) {
        int y=ver[i];
        if(y==pre) continue;
        dfs(y,x);
    }
}

int ask(int x,int k) {
    for(int i=0;i<=22;i++) {
        if((k>>i)&1) x=fa[x][i];
    }
    return x;
}

void query(int x,int fa) {
    for(int i=h[x];i;i=ne[i]) {
        int y=ver[i];
        if(y==fa) continue;
        query(y,x);
        ans[x]+=ans[y];
    }
}

void solve() {
    cin>>n;
    int x,y,d;
    for(int i=2;i<=n;i++) {
        cin>>x>>y;
        add(x,y); add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++) {
        cin>>d; y=ask(i,d+1);
        ans[i]++; ans[y]--;
    }
    query(1,0);
    for(int i=1;i<=n;i++) {
        if(i==1) cout<<ans[i];
        else cout<<" "<<ans[i];
    }
}

int main(){
    //freopen("data.in","r",stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T=1; //cin>>T;
	while(T--) {
        //init();
        solve();
	}
	return 0;
}