摘要:NOI plus模拟

10162020机房赛

来自中山的题,当时中山的做起来都特别拉跨,难度不小.

T1

题目分析

正解大概是倒序考虑,然后只有前面的操作可能产生贡献,并查集合并这些操作.

细节啥的也没搞懂,但是写得好的暴力加编译优化可以水过去,不过在场上只有拿70的.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=6000010;
lxl n,k,tmpnow;
char s[big],tmp[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
int main(void)
{
scanf("%s",s+1);
k=read(),n=read();
while(n--)
{
lxl l=read(),r=read(),len(r-l+1),point(r);
if(r>k)continue;
tmpnow=0;
for(R int i(r+1);i<=k-len;++i)tmp[++tmpnow]=s[i];
for(R int i(1);i<=k-len-r;++i)s[i+r+len]=tmp[i];
for(R int i(l+((l+1)&1));i<=r;i+=2)s[++point]=s[i];
for(R int i(l+(l&1));i<=r;i+=2)s[++point]=s[i];
}
for(R int i(1);i<=k;++i)printf("%c",s[i]);endl;
return 0;
}

T2

题目分析

转化问题然后高阶图论,一点不会(趴…),打了个阶乘暴力和一个特殊情况拿了20.

代码(20pts)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define INF 0x3f3f3f3f
#define R register
typedef long long lxl;
const lxl big=200010,p=1e9+7;
lxl n,ans,nlp=1;
lxl map[6][6],a[11],vis[11];
std::vector<lxl>xh[big],yh[big];
inline lxl FastPow(lxl a,lxl b)
{
lxl sum(1);
for(;b;b>>=1,a=a*a%p)(b&1)&&(sum=sum*a%p);
return sum;
}
inline lxl read()
{
char c=getchar();
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=x*10+(c-'0'),c=getchar());
return f*x;
}
void dfs(lxl ard)
{
if(ard==n+n)
{
lxl nmap[6][6],sum(0);
for(R int i(1);i<=n;++i)for(R int j(1);j<=n;++j)nmap[i][j]=map[i][j];
for(R int i(1);i<=ard;++i)
{
if(a[i]<=n){for(R int j(1);j<=n;++j)if(nmap[a[i]][j]){nmap[a[i]][j]=0,++sum;break;}}
else for(R int j(1);j<=n;++j)if(nmap[j][a[i]-n]){nmap[j][a[i]-n]=0,++sum;break;}
}
if(sum==n+n)++ans;
return;
}
for(R int i(1);i<=n+n;++i)
{
if(vis[i])continue;
vis[i]=true,a[ard+1]=i;
dfs(ard+1);
vis[i]=false,a[ard+1]=0;
}
}
int main(void)
{
n=read();
if(n<=5)
{
for(R int i(1);i<=n+n;++i)
{
nlp=nlp*i%p;
lxl x=read(),y=read();
map[x][y]=true;
}
dfs(0);
printf("%lld\n",ans*FastPow(nlp,p-2)%p);
}
else
{
for(R int i(1);i<=n+n;++i)
{
lxl x=read(),y=read();
xh[x].push_back(i),yh[y].push_back(i);
}
lxl flag=0;
for(R int i(2);i<=n;++i)if(xh[i].size()>1)flag+=xh[i].size()-1;
if(flag>2){printf("0\n");return 0;}
printf("%lld\n",FastPow(2,p-2));
}
return 0;
}

T3

题目分析

顶尖数学题,一点不会,考场上没开这题.

代码(0pts)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define INF 0x3f3f3f3f
#define R register
typedef long long lxl;
inline lxl read()
{
char c=getchar();
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=x*10+(c-'0'),c=getchar());
return f*x;
}
int main(void)
{
return 0;
}

总结

这下是什么难度的题都见识过了.

先开的T1,没什么思路,想了想直接打模拟了,觉得用splay来维护可以比暴力更优,splay写得比较熟于是就直接上去打了,但是在删除子树的时候没把节点旋到根更新size导致之后的find死循环于是爆零.暴力模拟其实也挺好写,拿70是很容易的.

T1花掉了2个小时,大部分时间花在调试上,还是得多熟悉平衡树和lct这些容易出错的数据结构,考场上才能快速现写出来,而且有些东西是特别不好调的,就比如splay调试需要每次旋转都画一张图,多项式(虽然联赛不考)基本没有调试可能,就得尽量一遍写对.

然后看T2,觉得是个期望DP,草稿纸上堆了会样例,想不出怎么转移,就写了阶乘的暴力,推了会部分分的特殊情况,拿了暴力的15分和特殊情况分的5分,还有10分的特殊情况分没时间写了.

T3没时间做了,有30分左右是可做的.