题解：P11965 [GESP202503 七级] 等价消除

本以为七级第一题五分钟就过是道黄很离谱了，结果搞了赛时搞了一个半小时的第二题是橙题，自愧不如。

采取桶的方式，记录当前状态下各种结尾的个数，采取二进制节约空间。注意所有字母都只有

0

个的结尾开始赋值为

1

。

CPP

#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#include <bits/stdc++.h>
#define ll long long 

ll len,ans;

ll cnt[1<<26],now[35];

std::string s;

int main()
{
    std::cin>>len>>s;
    s=" "+s;
    cnt[0]=1;
    for(int i=1;i<=len;i++)
	{
		int t=0;
        for(int j=0;j<26;j++)
        {
			if(j==s[i]-'a')
			{
				now[j]=!now[j];
			}
			if(now[j])
			{
				t+=(1<<j);
			}
		}
        ans+=cnt[t];
        cnt[t]++;
    }
	std::cout<<ans<<std::endl;
    return 0;
}

当然也可以用一个数记录当前状态，但我懒得打。

后记（有感）

第一题这么简单的题竟然是道黄题，这题思路我考场想了

1

个小时，差点放弃了。

还有就是考试的数据太水了。顺便警示大家：

CPP

cnt[0]=1;

千万不要在定义时就写成：

CPP

ll cnt[1<<26]={1}

因为你会发现它编译不出来。考试的时候一直都是这么写的，就只开了 1<<23 的大小，当时拿到了 12.5 分，虽然编译器开不下，但是把它改成 1<<24 又冒险交了一发，结果分数 17.5 了。开成 1<<25 就莫名满分了，但是开 1<<26 是会报错的。其实如果数据严一些，我只能拿到 10 分，结果却莫名多了 15 分，运了。

题解：P11965 [GESP202503 七级] 等价消除

文章操作

后记（有感）

相关推荐

评论

题解：P11965 [GESP202503 七级] 等价消除