Array[3](NOIP模拟赛[1])=>{Array(Problem(连续出现的字符),Problem(HH的项链),Problem(关押罪犯))}

Log:OJ比赛模块半死不活,添加还需手工。。。。

部分页面免登录查看完成。。。。。

考完数学之后整个人都不好了

Scoreboard of NOIP模拟赛

#UsernameName连续出现的字符
100
关押罪犯
100
HH的项链
100
Total
300
1zyfzyf张烨飞100
00:44
100
02:37
-200
03:31
2copyright张淇80
00:31
100
02:38
-180
03:25
3chestnut管理员100
00:11
50
01:03
-150
01:25
4shiniestasia李松轩100
00:43
10
02:40
10
01:28
120
05:07
518166167张家辉100
01:02
10
01:57
-110
03:09
6yigong许开彦100
01:23
10
01:54
-110
03:43
7heheda吴梦堉100
01:54
10
02:34
-110
04:43
8pang陈浩南100
00:18
--100
00:23
9tjtzgby郭博源100
01:10
--100
01:15
102327129970王科澳100
01:12
0
02:13
-100
03:55
11592ddd文卓达100
01:54
0
02:07
-100
04:11
12jyjy田宇航100
01:00
0
02:53
0
02:11
100
06:20
13mmaayy马悦程80
01:28
10
02:16
-90
03:54
14czm陈张萌80
00:45
10
02:52
0
01:47
90
05:45
15l90537517刘宇飞80
00:47
--80
00:52
161036850657邸新澈40
00:44
--40
00:54
17zhang张品先40
02:00
--40
02:10
18jeffrey刘沛臻40
02:14
--40
02:19
19www王奕航0
01:43
--0
01:48

T1大水题,为提高均分,让高一党超越高二作出了极大的贡献
#include<cstdio>
#include<iostream>
using namespace std;
char a[1010];
int k;
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	cin>>k>>a;
	int i=0,count=1;
	char before='\0';
	while(a[i]!='\0'){if(before==a[i]){if(++count==k){cout<<a[i];return 0;}}else{count=1;before=a[i];}i++;}
    cout<<"No";
}

T2 并查集,然而完全迷糊的写错依然有50分,,,数据太良心,,,,据说T1看错题都有80.。。。
#include<cstdio>
#include<algorithm>
using namespace std;
int bcj[40010],n,m;
struct edge{
	int u,v,w;
}edges[100010];
int getfa(int x){
	return bcj[x]==x?x:bcj[x]=getfa(bcj[x]);
}
int comp(const edge &a,const edge &b){return a.w>b.w;}
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&edges[i].u ,&edges[i].v,&edges[i].w);
	sort(edges+1,edges+m+1,comp);
	for(int i=1;i<=m;i++)bcj[i]=i;
	for(int i=1;i<=m;i++)
		if(getfa(edges[i].u)!=getfa(edges[i].v)){
			bcj[getfa(edges[i].u)]=getfa(edges[i].v);
		}else{
			printf("%d",edges[i].w);
			return 0;
		}
	printf("0");
}

这都有50分。。。。。。

以下是田大神的正解%%%%%%%%%

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
int n,m,fa[2000000];
struct edge{int from,to,len;}hh[2000000];
bool cmp(const edge &a,const edge &b) {return a.len>b.len;}
int find(int x){
 if(fa[x]==x) return x;
 return  find(fa[x]);
 }
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{  scanf("%d%d%d",&hh[i].from,&hh[i].to,&hh[i].len);
	}
	sort(hh+1,hh+1+m,cmp);
	for(int i=1;i<=2*n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int x=find(hh[i].from),y=find(hh[i].to);
		if(x==y)
		{
			cout<<hh[i].len<<endl;
			return 0;
		}
		fa[x]=find(hh[i].to+n);
		fa[y]=find(hh[i].from+n);
	}
	cout<<0<<endl;
	return 0;
}

T3线段树。。。然而没听懂。。。。。周六的课貌似还需要重学一遍Orz

黄学长的代码。。。。。。

这题首先在线是没法做的,所以我们可以考虑离线算法

首先记录下每种颜色的下一种颜色所在的位置

将所有询问按照左端点进行排序

将所有颜色的第一个点x a[x]++

然后从左往右扫

扫到一个点x将a[next[x]]++

碰到一个询问l,r输出sum[r]-sum[l-1]

其中sum是a数组的前缀和

求前缀和可以用树状数组

还是理解不能。。。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,mx;
int a[50005],next[50005],t[50005];
int p[1000005];
struct data{int l,r,id,ans;}q[200005];
bool cmp1(data a,data b)
{return a.l==b.l?a.r<b.r:a.l<b.l;}
bool cmp2(data a,data b)
{return a.id<b.id;}
int lowbit(int x){return x&(-x);}
void update(int x,int v)
{
	for(int i=x;i<=n;i+=lowbit(i))
	    t[i]+=v;
}
int ask(int x)
{
	int tmp=0;
	for(int i=x;i>0;i-=lowbit(i))
	    tmp+=t[i];
	return tmp;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	    a[i]=read(),mx=max(mx,a[i]);
	for(int i=n;i>0;i--)
	    next[i]=p[a[i]],p[a[i]]=i;
	for(int i=1;i<=mx;i++)
	    if(p[i])update(p[i],1);
	m=read();
	for(int i=1;i<=m;i++)
	    q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+m+1,cmp1);
	int l=1;
	for(int i=1;i<=m;i++)
	{
		while(l<q[i].l)
		{
			if(next[l])update(next[l],1);
			l++;
		}
		q[i].ans=ask(q[i].r)-ask(q[i].l-1);
	}
	sort(q+1,q+m+1,cmp2);
	for(int i=1;i<=m;i++)
	    printf("%d\n",q[i].ans);
	return 0;
}

 

此条目发表在JCYZOJ, 并查集, 线段树分类目录。将固定链接加入收藏夹。