https://ac.nowcoder.com/acm/contest/1108#question

A-字符画 签到题 照着打就行

#include<iostream>
using namespace std;
char q[2020];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        q[i]='.';
 printf("ooo%sooo%sooo%sooo\n",q,q,q);
 printf("..o%so.o%s.o.%so.o\n",q,q,q);
 printf("ooo%so.o%s.o.%sooo\n",q,q,q);
 printf("o..%so.o%s.o.%so.o\n",q,q,q);
 printf("ooo%sooo%sooo%sooo\n",q,q,q);
    return 0;
}

B-2018-div-matrix

题意：一个矩阵 左上角 是2018 左边和下边都是2018的约束 这样推下去 给n m
问多少个矩阵符合要求
题解：玄学过题
发现规律

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include <unordered_set>
#include <bitset>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int maxn = 2005;
const int mod = 1e9 + 7;
 
ll dp[maxn][maxn];
 
void init() {
    dp[0][0] = 1;
    for (int i = 0; i < maxn; i++) {
        for (int j = 0; j < maxn; j++) {
            if (i) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
            }
            if (j) {
                dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod;
            }
        }
        //for (int i = 0; i < maxn; i++) {
        //  for (int j = 0; j < maxn; j++) {
        //      cout << dp[i][j];
        //  }
        //  cout << endl;
        //}
    }
}
 
int main()
{
    init();
    ios::sync_with_stdio(0);
    int n, m;
    while (cin >> n >> m) {
        ll w = (dp[n][m] - 1) % mod;
        cout << 1LL * w * w % mod << endl;
    }
}

C-时间旅行

签到题

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,m;
    while(~scanf("%lld%lld",&n,&m))
    {
        if(m<n)
            printf("%lld\n",n);
        else{
            printf("%lld\n",n+m-n+1);
        }
    }
    return 0;
}

H-千万别用树套树

树状数组 线段树都能过

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, q;
int b[maxn];
int a[maxn];
int num[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void update1(int x)
{
    while (x <= n)
    {
        a[x]++;
        x += lowbit(x);
    }
}
void update2(int x)
{
    while (x <= n)
    {
        b[x]++;
        x += lowbit(x);
    }
}
int query(int x, int c[])
{
    int res = 0;
 
    while (x)
    {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
int main()
{
    while (~scanf("%d%d", &n, &q))
    {
        memset(num, 0, sizeof(num));
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        int cnt = 0;
        while (q--)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            if (x == 1)
            {
                cnt++;
                if (y == z)
                {
                    num[y]++;
                }
                 
                    update2(z);
                    update1(y);
                 
            }
            else
            {
                int ans = query(y, a) - query(z - 1, b);
                if (z - y == 2)ans += num[y + 1];
                printf("%d\n",ans);
            }
        }
    }
}

J-买一送一

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
int num[maxn];
int before[maxn];
int vis[maxn];
int p[maxn];
vector<int>v[maxn];
ll ans[maxn];
void dfs(int x,ll tmp)
{
    int len=v[x].size();
    for(int i=0;i<len;i++)
    {
        if(!vis[p[x]])tmp++;
        vis[p[x]]++;
        int vv=v[x][i];
        ans[vv]=ans[x]+tmp-before[p[vv]];
        int cnt=before[p[vv]];
        before[p[vv]]=tmp;
        dfs(vv,tmp);
        vis[p[x]]--;
        if(vis[p[x]]==0)tmp--;
        before[p[vv]]=cnt;
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0;i<=n;i++)
        {
            v[i].clear();
            vis[i]=0;
            ans[i]=0;
            before[i]=0;
        }
        int x;
        for(int i=2;i<=n;i++)
        {
            scanf("%d" , &x);
            v[x].push_back(i);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&p[i]);
        }
        dfs(1,0);
        for(int i=2;i<=n;i++)
        {
            printf("%lld\n",ans[i]);
        }
    }
 }

K-use fft
题意：给两个多项式 求他们的乘积的各项系数的和
看起来很难 其实求个前缀和然后求随便过的

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<cstring>
#include <unordered_set>
#include <bitset>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
using namespace std;

ll a[maxn], b[maxn];
ll sum[maxn << 1];

int main() {
	ios::sync_with_stdio(0);
	int n, m, l, r;
	while (cin >> n >> m >> l >> r) {
		for (int i = 1; i <= n + 1; i++)
			cin >> a[i];
		for (int i = 1; i <= m + 1; i++) {
			cin >> b[i];
			sum[i] = (sum[i - 1] + b[i] + mod) % mod;//前缀和
		}
		for (int i = m + 2; i <= r+1; i++) {
			sum[i] = sum[i - 1];//补全
		}
		ll ans = 0;
		for (int i = 1; i <= n + 1; i++) {
			ans = (ans + a[i] * (sum[r + 1] - sum[l] + mod) % mod + mod) % mod;//求和
			if (l > 0) l--;//更新范围
			if (r >= 0) r--;
			else break;
		}
		cout << ans << endl;
	}
	return 0;
}