2019徐州站网络赛总结

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;
}

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114859.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • BeanUtils.populate 使用笔记

    BeanUtils.populate 使用笔记最近在学习网站开发,在后端获取网站请求数据的时候用到了BeanUtils.populate()方法,具体用法是:BeanUtils.populate(objectobj,Map<String,String[]>map);于是我就在想这个方法是怎么把map中的数据封装到obj对象里的。打开源码看,看别人写的代码是真难受,看了半天还是没看懂。上网搜了一下,发现多数都是在讲用法…

  • java注解拦截_轻松实现java拦截器+自定义注解

    java注解拦截_轻松实现java拦截器+自定义注解本文将用简洁的代码构建一个springboot的拦截器。拦截器的使用很简单,定义一个自己的拦截器,向配置中添加一下就可以使用。为了方便,之后又引入了注解。目录和概述概述假设需求:访问项目的controller是都要进行”token验证”,除了某些像登录之类的方法。项目结构:TokenInterceptor.java自定义拦截器InterceptorConfig.java添加拦截器进入项目NoN…

  • SSM框架——详细整合教程(Spring+SpringMVC+MyBatis)

    SSM框架——详细整合教程(Spring+SpringMVC+MyBatis)使用SSM(Spring、SpringMVC和Mybatis)已经有三个多月了,项目在技术上已经没有什么难点了,基于现有的技术就可以实现想要的功能,当然肯定有很多可以改进的地方。之前没有记录SSM整合的过程,这次刚刚好基于自己的一个小项目重新搭建了一次,而且比项目搭建的要更好一些。以前解决问题的过程和方法并没有及时记录,以后在自己的小项目中遇到我再整理分享一下。这次,先说说三大框架整合过程。个人认

  • 如何严格设置php中session过期时间

    如何严格设置php中session过期时间

  • Git创建分支和查看分支命令「建议收藏」

    Git创建分支和查看分支命令「建议收藏」branch:分支 是指在开发主线中分离出来的,做进一步开发而不影响到原来的主线Git存储的不是一系列的更改集,而是一系列快照,当你执行一次commit时,git存储一个commit对象,她包含它包含一个指针指向你当前需要提交的内容的快照。master分支是在gitinit命令运行时默认创建一个分支,并命名为master1.查看分支gitbranch:列出本地已经存在的分支,…

  • java的this怎么理解

    java提供了一个this关键字,this关键字总是指向调用该方法的对象。根据this出现位置的不同,this作为对象的默认引用有两种情形:构造器中引用该构造器正在初始化的对象;在方法中引用调用该方法的对象。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号