比赛链接：https://codeforces.com/contest/434
中国人出的浓度很高的一场
kitahara haruki - 北原春希（WA2）
Kuriyama Marai - 栗山未来（境界的彼方）
Ryouko - 御门凉子（出包王女）
Nanami - 七海千秋（弹丸论破）
Tachibana Kanade - 立华奏（ab）
Furukawa Nagisa - 古河渚（cl）
2A 2B
水题
// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int inf = 1e9, INF = 0x3f3f3f3f;
int cnt[4];
signed main(){
int tot=0,n;scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);x /= 100;
++ cnt[x];
tot += x;
}
if(tot&1){
puts("NO");
return 0;
}
tot /= 2;
for(int i=0;i<=cnt[1];i++){
int j = tot - i;
if(j&1)continue;
j /= 2;
if(j <= cnt[2]){
puts("YES");
return 0;
}
}
puts("NO");
return 0;
}
// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int inf = 1e9, INF = 0x3f3f3f3f,maxn=2e5+5;
int n,a[maxn];
LL sum[maxn], sum2[maxn];
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]), sum[i] = sum[i-1] + a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)sum2[i] = sum2[i-1] + a[i];
int m;scanf("%d",&m);
while(m --){
int ty,l,r;scanf("%d%d%d",&ty,&l,&r);
if(ty == 1)printf("%I64d\n",sum[r] - sum[l-1]);
else printf("%I64d\n",sum2[r] - sum2[l-1]);
}
return 0;
}
2C/1A
好像说改中位数就行了
我做麻烦了。。
首先观察到如果要改，那么一定改成这个数对应的很多个邻居中的一个一定最优
然后枚举改成哪个邻居最优，这个用前缀和处理一下就很容易计算了
注意两个相邻数相同的话会出错，注意特判一下
// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5 + 5;
vector<int>vi[maxn];
int n,m;
int a[maxn];
LL ans = 0;
LL res[maxn];
LL sum2[maxn],b[maxn];
signed main(){
scanf("%d%d",&m,&n);
if(n == 1)return puts("0"),0 ;
for(int i=1;i<=n;i++)scanf("%d",&a[i]), b[i] = a[i];
for(int i=1;i<=n-1;i++)ans += abs(a[i] - a[i+1]);
for(int i=1;i<=n;i++){
if(i == 1){
if(a[i]!=a[i+1])vi[a[i]].push_back(a[i+1]); res[a[i]] += abs(a[i] -a[i+1]);
}
else if(i == n){
if(a[i]!=a[i-1])vi[a[i]].push_back(a[i-1]); res[a[i]] += abs(a[i] -a [i-1]);
}
else{
if(a[i]!=a[i+1])vi[a[i]].push_back(a[i+1]);
if(a[i]!=a[i-1]) vi[a[i]].push_back(a[i-1]);
res[a[i]] += abs(a[i]-a[i-1]) + abs(a[i] - a[i+1]);
}
}
LL rr = ans;
for(int i=1;i<=m;i++)if(vi[i].size()){
sort(vi[i].begin(), vi[i].end());
int nvi = vi[i].size();
for(int j=0;j<nvi;j++)sum2[j+1] = sum2[j] + vi[i][j];
sum2[nvi + 1] = 0;
LL r = 1e18;
for(int j=1;j<=nvi;j++){
int cur = vi[i][j - 1];
LL curm = sum2[nvi] - sum2[j] - sum2[j-1] + 1ll * (2*j-nvi-1) * cur;
r = min(r, curm);
}
rr = min(rr, ans + r - res[i]);
}
printf("%I64d\n",rr);
return 0;
}
2D/1B
https://www.luogu.com.cn/blog/DenyTianly/solution-cf433d
2E/1C
多串匹配 联想到AC自动机
又要统计 \([L,R]\) 的个数，数位dp
所以思路就很清晰了：先对 \(n\) 个串建出AC自动机，然后设 \(dp[i][0/1][0/1][acstate][val]\) 表示考虑到第 \(i\) 位，是否顶上界、是否有前导0、AC自动机的结点、当前的权值是 \(val\) 的方案数
每次转移的时候枚举当前的数，然后AC自动机跳，看能匹配到多少个串即可
处理一下特例：有多个前导0的时候，AC自动机不跳
// by SkyRainWind
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 10005,mod=1e9+7;
int n,m,k;
int dp[205][2][2][205][505]; // !!!!! bigger
int l0, r0, le[maxn], ri[maxn], num[maxn];
struct AC{
int lst[maxn];
int tr[maxn][27],cnt;
int val[maxn]; // 多少个以 i 结点结尾的单词
int fail[maxn];
AC(){cnt=0;memset(val,0,sizeof val);}
void insert(int *s, int ns,int v){
int p=0;
for(int i=1;i<=ns;i++){
int k = s[i];
if(!tr[p][k])tr[p][k] = ++ cnt;
p = tr[p][k];
}
val[p] += v;
}
void build(){
queue<int>Q;
Q.push(0);
while(!Q.empty()){
int u = Q.front();Q.pop();
for(int i=0;i<26;i++)
if(tr[u][i]){
fail[tr[u][i]] = u ? tr[fail[u]][i] : 0;
if(val[fail[tr[u][i]]])lst[tr[u][i]] = fail[tr[u][i]];
else lst[tr[u][i]] = lst[fail[tr[u][i]]];
Q.push(tr[u][i]);
}else tr[u][i] = tr[fail[u]][i];
}
}
int query(int *t,int nt){
int p=0, res=0;
for(int i=1;i<=nt;i++){
p = tr[p][t[i]];
if(val[p])res += val[p];
int v = lst[p];
while(v){
if(val[v])res += val[v];
v = lst[v];
}
}
return res;
}
int query(int acst){
int p=acst, res=0;
if(val[p])res += val[p];
int v = lst[p];
while(v){
if(val[v])res += val[v];
v = lst[v];
}
return res;
}
}ac;
int da[10005], dlen;
// lim==1 在上界 lead0==1 有前导零
int dfs(int cur,int lim,int lead0,int acst,int val){
int &dd = dp[cur][lim][lead0][acst][val];
if(cur == dlen + 1){
if(lead0 == 1)return 0;
return dd = 1;
}
if(~dd)return dd;
int up = lim ? da[cur] : m-1;
int res = 0;
for(int i=0;i <= up;i++){
if(i == 0 && lead0){
res += dfs(cur+1, 0, 1, acst, val);
if(res>=mod)res-=mod;
}else{
int tt = val + ac.query(ac.tr[acst][i]);
if(tt <= k){
res += dfs(cur+1, lim && i == up, 0, ac.tr[acst][i], tt);
if(res>=mod)res-=mod;
}
}
}
return dd = res;
}
int solve(int *a,int len){
memset(dp, -1, sizeof dp);
for(int i=1;i<=len;i++)
da[i] = a[i];
da[len+1] = 0;
dlen = len;
int t = dfs(1,1,1,0,0);
return t;
}
int solve0(int *a,int len){
return ac.query(a, len) <= k;
}
signed main(){
scanf("%d%d%d",&n,&m,&k);
scanf("%d",&l0);
for(int i=1;i<=l0;i++)scanf("%d",&le[i]);
scanf("%d",&r0);
for(int i=1;i<=r0;i++)scanf("%d",&ri[i]);
for(int i=1;i<=n;i++){
int ns;scanf("%d",&ns);
for(int j=1;j<=ns;j++)
scanf("%d",&num[j]);
int v;scanf("%d",&v);
ac.insert(num, ns, v);
}
ac.build();
printf("%d\n",(mod + (solve(ri,r0) - solve(le,l0))%mod + solve0(le,l0))%mod);
return 0;
}