2019徐州站网络赛总结

这次没想到有几道签到题，嗯，就做了两道。

The hot summer came so quickly that Xiaoming and Xiaohong decided to buy a big and sweet watermelon. But they are two very strange people. They are even-numbered enthusiasts. They want to cut the watermelon in two parts, and each part weighs two times as much as a kilogram .They quickly decide which melon to buy. Do you know if you want to buy this melon?

Input

Only one line contains one integer ww (1\leq w\leq 100)(1≤w≤100),units are kilograms.

Output

If it can meet the requirements, you will output YES, otherwise output NO.

样例输入复制

8

样例输出复制

YES

反正就是切西瓜，开始写成2的指数倍了，后来发现只要是2的倍数就可以，除了2。

太简单了就不打了、

再就是一个kmp算法的题：

Carneginon was a chic bard. But when he was young, he was frivolous and had joined many gangs. Recently, Caneginon was to be crowned, because the king was shocked by his poems and decided to award him the gold medal lecturer. Therefore, Most of people in the Kingdom came to visit him.

However, as a medal lectirer, Carneginon must treat the visitors kindly, including elders and younger generations. In order to maintain order, every visitor received a license with a magic field engraved on it. And the magic field on the licence was made up of lowercase letters.

Carneginon had a unique licence, which could judge whether others are his older or younger. Now, we assume that the sequence on Carneginon’s licence is TT and the sequence on visitors’ licence is SS. For each visitor,

• If the length of TT is longer than the length of SS, it’s obviously that the visitor is younger. And if SS is a substring of TT, Carneginon would call the visitor my child!. Otherwise, Carneginon would call the visitor oh, child!.

• If the length of TT is less than the length of SS, it’s obviously that the visitor is elder. And if TT is a substring of SS, Carneginon would call the visitor my teacher!. Otherwise, Carneginon would call the visitor senior!.

• Of course, if the length of TT is equal to the length of SS, the visitor is Carneginon’s peer. And if TT is equal to SS, it shows that the visitor entered through an improper way and Carneginon would shout jntm!. Otherwise, Carneginon would call the visitor friend!.

Now, you know the TT (Carneginon’s licence), qq (the number of visitors) and each visitor’s licence(S_iSi​). Can you judge what Caneginon needs to say when he sees every visitor?

Input

The first line is a string TT, representing Carneginon’s license.

The second line is and integer qq, which means the number of visitors.

Then mm lines, for each line, there is a string SS, denoting the visitor’s license.

1 \leq |T| \leq 10^51≤∣T∣≤105, 1 \leq |S| \leq 10^51≤∣S∣≤105, 1 \leq q \leq 10001≤q≤1000

It is guaranteed that q \times (|S|+|T|) \leq 10^7q×(∣S∣+∣T∣)≤107.

Output

There are qq lines.

For each SS, output what Carneginon should say correctly.

样例输入复制

abcde
6
abcde
aaaaa
abcd
aaaa
abcdef
abccdefg

样例输出复制

jntm!
friend!
my child!
oh, child!
my teacher!
senior!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 1e6+5;
//char s[maxn],p[maxn];
int _next[maxn];
int n, m, t;
void get_next(char p[maxn]) 
{
	int j=0,k=-1;
	_next[0] = -1;
	int m=strlen(p);
	while(j<m-1)
	{
		if(k==-1 || p[j]==p[k]) {
			j++;
			k++;
			_next[j] = k;
		} else
			k = _next[k];
		}
}
int kmp( char s[maxn], char p[maxn] )
{
	int i=0,j=0;
	int ans=0;
	int n=strlen(s);
	int m=strlen(p);
	while(i<n) {
		if(j==-1 || s[i]==p[j]) {
			i++;
		    j++;
		} else
			j = _next[j];
		if(j==m)
		{
			ans++;
		}
	}
	return ans;
}
int main() 
{
	char s1[maxn];
	char s2[maxn];
	scanf("%s",s1);
	scanf("%d",&t);
	int as=strlen(s1);
	while(t--)
	{
		int sum = 0;
		scanf("%s",s2);
		int bs=strlen(s2);
		if(as==bs)
		{
			get_next(s2);
			sum	= kmp(s1,s2);
			if(sum==1)
				printf("jntm!\n");
			else
				printf("friend!\n");
			
		}
		if(as>bs)
		{
			get_next(s2);
			sum	= kmp(s1,s2);
			if(sum>=1)
				printf("my child!\n");
			else
				printf("oh, child!\n");
		}
		if(as<bs)
		{
			get_next(s1);
			sum	= kmp(s2,s1);
			if(sum>=1)
				printf("my teacher!\n");
			else
				printf("senior!\n");	
		}
	}
	return 0;
} 

然后就是b题就卡壳了

•  262144K

There are nn points in an array with index from 11 to nn, and there are two operations to those points.

1: 1 \ x1 x marking the point xx is not available

2: 2 \ x2 x query for the index of the first available point after that point (including xx itself) .

Input

n\quad qnq

z_1 \quad x_1z1​x1​

\vdots⋮

z_q\quad x_qzq​xq​

qq is the number of queries, zz is the type of operations, and xx is the index of operations. 1≤x<n<10^91≤x<n<109， 1 \leq q<10^61≤q<106 and zz is 11 or 22

Output

Output the answer for each query.

样例输入复制

5 3
1 2
2 2
2 1

样例输出复制

3
1

题解代码如下：

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 100;
unordered_map<int, int> fa;

int findfa(int x) {
    if (!fa.count(x)) return x;
    return fa[x] = findfa(fa[x]);
}


int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    int n, q;
    scanf("%d %d", &n, &q);
    int op, x;
    while (q--) {
        scanf("%d %d", &op, &x);
        if (op == 1) {
            fa[x] = findfa(x + 1);
        } else {
            int ans = findfa(x);
            if (ans > n) ans = -1;
            printf("%d\n", ans);
        }
    }
    return 0;
}

其实是并查集知识：。。
q的值比较小，所以解题应该从q入手
用并查集模拟实现一个链表
用map模拟并查集，初始时每个点的父亲指向后面第一个可用的点。 当删除一个点i时，令x的父亲等于x+1的父亲 查询时直接输出 x 的父亲 

再就是e题也提交比较多

XKC , the captain of the basketball team , is directing a train of nn team members. He makes all members stand in a row , and numbers them 1 \cdots n1⋯n from left to right.

The ability of the ii-th person is w_iwi​ , and if there is a guy whose ability is not less than w_i+mwi​+m stands on his right , he will become angry. It means that the jj-th person will make the ii-th person angry if j>ij>i and w_j \ge w_i+mwj​≥wi​+m.

We define the anger of the ii-th person as the number of people between him and the person , who makes him angry and the distance from him is the longest in those people. If there is no one who makes him angry , his anger is -1−1 .

Please calculate the anger of every team member .

Input

The first line contains two integers nn and m(2\leq n\leq 5*10^5, 0\leq m \leq 10^9)m(2≤n≤5∗105,0≤m≤109) .

The following  line contain nn integers w_1..w_n(0\leq w_i \leq 10^9)w1​..wn​(0≤wi​≤109) .

Output

A row of nn integers separated by spaces , representing the anger of every member .

样例输入复制

6 1
3 4 5 6 2 10

样例输出复制

4 3 2 1 0 -1

题目大意：第i 个元素的愤怒值定义为：在i 右侧的所有满足a[j]>=a[i]+m 中 最大的 j−i−1 ，若不存在这样的数则值为−1 -。输出每个元素的愤怒值。

思路：也算是签到题吧。用线段树维护区间最大值。那么要查询的其实就是[i+1,n] 内满足a[j]>=a[i]+m 的最大的j ，因此考虑优先查询右子树，最后返回下标即可。可惜我当时没看懂。
————————————————
 

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define fuck(x) cout << (x) << endl
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e5 + 10;
const int M = 1e4 + 10;

int n, m;
int a[N];
int tr[N << 2];

void build(int l, int r, int rt){
    if(l == r){
        tr[rt] = a[l];
        return;
    }
    int m = l + r >> 1;
    build(lson);
    build(rson);
    tr[rt] = max(tr[rt << 1], tr[rt << 1 | 1]); // pushup(rt);
}

int query(int l, int r, int rt, int sum){
    if(l == r){
        return l;
    }
    int m = l + r >> 1;
    if(tr[rt<<1|1] >= sum)       // 先找右边的
        return query(rson, sum);      
    else {						// 右边没有再考虑左边
        if(tr[rt<<1] >= sum)
            return query(lson, sum);
        else {				// 都没有就不行了
            return -1;               
        }
    }    
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    build(1, n, 1);
    for(int i = 1; i <= n; i++){
        int ans = query(1, n, 1, a[i]+m);
        if(ans == -1){	// 没有找到
            printf("-1%c", " \n"[i == n]);
        }else {
            if(ans > i)	
                printf("%d%c", ans - i - 1, " \n"[i == n]);
            else	// 找到了，但是不在 i 的右边
                printf("-1%c", " \n"[i == n]);
        }
    }
    return 0;
}

课下再把线段树的知识巩固巩固。。。