qijuntong2012's blog

低调做人，高调做事

0%

2024.10.5赛后总结

发表于 分类于

2024.10.5 赛后总结

比赛记录

成绩：\(100+40+0+0=140\space\texttt{pts}\)

难度：\(\textcolor{orange}{\texttt{橙}}\space\textcolor{yellow}{\texttt{黄}}\space\textcolor{yellow}{\texttt{黄}}\space\textcolor{green}{\texttt{绿}}\)

反思

  • 推公式的时候一定要全面思考，作者为此浪费 \(1\space\texttt{h}\)。
  • 赛时如果样例WA了没调不出来就赶紧打暴力，不要将错就错。
  • 就算没时间思考也要骗分，本人就为此丢掉 \(30\space\texttt{pts}\) 。

题目

A

题面

一个序列，求这个序列所有非空子序列的和。

思路

设第 \(i\) 个数在所有子序列出现的次数为 \(a_i\) ，那： \[ a_i=a_{i-1}+n-2i \]

std

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=1e9+7;
const int N=1e7+10;
int a[N];
int n;
int ans=0;
signed main() 
{
	freopen("score.in","r",stdin);
	freopen("score.out","w",stdout);	
	scanf("%lld",&n);
	a[1]=n;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%lld",&x);
		ans+=(a[i]*x);
		ans%=Mod;
		a[i+1]=a[i]+(n-2*i);
	}
	printf("%lld\n",ans);
	return 0;
}

代码要点

十年OI一场空，不开 long long 见祖宗。

B

题面

一棵树有 \(n\) 个节点，\(n\) 条边，求从 \(i\) 点出发能到达点的最大点权和。

思路

拓扑排序处理环，根据环的答案计算不在环上节点的答案。

std

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
74
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
#define debug cerr<<"wssb\n";
int a[N],f[N],d[N],q[N],v[N],ans[N],n,l,r;
signed main() 
{
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>f[i];
		d[f[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(d[i]==0)
		{
			q[r]=i;
			r++;
		}
	}
	while(l<r)
	{
		int x=q[l];
		v[x]=1;
		d[f[x]]--;
		if(d[f[x]]==0)
		{
			q[r]=f[x];
			r++;
		}
		l++;
	}
	for(int i=1;i<=n;i++)
	{
		if(!v[i])
		{
			int x=i;
			int st=x;
			int sum=a[x];
			v[x]=1;
			while(f[x]!=st)
			{
				x=f[x];
				v[x]=1;
				sum+=a[x];
			}
			x=i;
			ans[x]=sum;
			while(f[x]!=st)
			{
				x=f[x];
				ans[x]=sum;
			}
		}
	}
	for(int i=r-1;i>=0;i--)
	{
		 int x=q[i];
		 ans[x]=a[x]+ans[f[x]];
	}
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<'\n';
	}
	return 0;
}

代码要点

如果用 DFS 找环，小心系统栈爆掉。

C

题面

询问以下格式的Python代码输出结果是什么。

1
2
3
4
5
ans=0
for A in range(a,b,c):
	for B in range(d,e,f):
		ans=ans+B
print(ans)

思路

数学题，等差数列优化就可以压缩时间复杂度。就是输入很麻烦。

std

后面两道题没来得及补，我就先复制一个。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn long long
#define x first
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define y second
const int N=1e6+5,INF=0x3f3f3f3f3f3f3f3f;
string s1,s2,s3,s4;
string s;
char c1,c2;
string S1,S2,S3,S4;
string a1,a2;
signed main(){
	freopen("output.in","r",stdin);
	freopen("output.out","w",stdout);
	int ans=0;
	cin>>s;
	cin>>s1>>c1>>s2>>s3;
	cin>>S1>>c2>>S2>>S3;
	cin>>a1>>a2;
	int a=0,b=0,c=0,d=0,e=0,f=0;
	int i;
	int t=1;
	for(i=6;s3[i]!=',';i++){
		if(s3[i]=='-'){t=-1;continue;}
		a=a*10+(s3[i]-'0');
	}
	a*=t;t=1;i++;
	for(;s3[i]!=',';i++){
		if(s3[i]=='-'){t=-1;continue;}
		b=b*10+(s3[i]-'0');
	}
	b*=t;t=1;i++;
	for(;s3[i]!=')';i++){
		if(s3[i]=='-'){t=-1;continue;}
		c=c*10+(s3[i]-'0');
	}
	c*=t;t=1;
	for(i=6;S3[i]!=',';i++){
		if(S3[i]=='-')
		{
			t=-1;continue;
		}
		if(S3[i]==c1)
		{
			d=-1919810;
			continue;
		}
		d=d*10+(S3[i]-'0');
	}
	d*=t;t=1;i++;
	for(;S3[i]!=',';i++){
		if(S3[i]=='-')
		{
			t=-1;continue;
		}
		if(S3[i]==c1)
		{
			e=-1919810;
			continue;
		}
		e=e*10+(S3[i]-'0');
	}
	e*=t;t=1;i++;
	for(;S3[i]!=')';i++){
		if(S3[i]=='-')
		{
			t=-1;continue;
		}
		if(S3[i]==c1)
		{
			f=-1919810;
			continue;
		}
		f=f*10+(S3[i]-'0');
	}
	f*=t;t=1;
	if(c<0)
	{
		t=-1;
	}
	for(int i=a;i*t<b*t;i+=c)
	{
		int d1,e1;
		if(d==-1919810)d1=i;
		else
		{
			d1=d;
		}
		if(e==-1919810)e1=i;
		else
		{
			e1=e;
		}
		int o=1;
		if(d1>e1)o=-1;
		// for(int j=d1;j*o<e1*o;j+=f)
		// {
			// ans+=j;
		// }
		if((f<0&&d1>e1)||(f>0&&d1<e1))ans+=(d1+((e1-d1-1)/f)*f+d1)*((e1-d1-1)/f+1)/2;
	}
	cout<<ans<<endl;
	return 0;
}

D

题面

又是抽象的题面……

思路

和昨天一样，还是dp。

std

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
#include<bits/stdc++.h>
using namespace std;
long long dp[200010];
long long s[200010];
long long f[30];
long long mod=1000000007;
int main(){
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	int m,k;
	cin >> m >> k;
	dp[0]=1;
	s[0]=1;
	memset(f,0,sizeof(f));
	string ss;
	cin >> ss;
	int n=ss.size();
	for(int i=1;i<=n;i++){
		
		char c;
		c=ss[i-1];
		int x=c-'a';
		//cout << f[x]-1 << " ";
		if(f[x]-1>=0)dp[i]=s[i-1]-s[f[x]-1];
		else dp[i]=s[i-1];
		dp[i]+=mod;
		dp[i]%=mod;
		s[i]=s[i-1]+dp[i];
		f[x]=i;
	}
	int la=s[n]-'a';
	for(int i=1;i<=m;i++){
		//cout << i+n << " ";
		int x=0;
		
		for(int j=1;j<k;j++){
			if(f[j]<f[x])x=j;
		}
		la=x;
		if(f[x]-1>=0)dp[n+i]=s[n+i-1]-s[f[x]-1];
		else dp[i+n]=s[i+n-1];
		dp[i+n]+=mod;
		dp[i+n]%=mod;
		s[i+n]=s[i+n-1]+dp[i+n];
		f[x]=i+n;
	}
	cout << s[n+m]%mod;
	return 0;
}

代码要点

还是要开 long long。