今天我们要来看看 Codeforces 2016-2017 年的一套训练题。
题目链接:https://codeforces.com/gym/101138
题意:给
个串,有两种操作,一种是给某个串加一个字符,另一种是求存不存在一个串是查询串的子串。强制在线。
题解:由于限制了总长,所以不同的长度不会太多(根号级别)。枚举长度匹配一下哈希就行。
自动机也是能搞的,但是没有hash写起来舒服。
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
#define PII pair <int,int>
#define fr first
#define sc second
#define mp make_pair
const ll base=37;
const int N=8e5+7;
char s[N];
int last_ans;
map<int,int> len;
multiset <ll> S;
ll p[N];
int lc[N];
ll Base[N],qu[N];
ll hsh(char *s){
ll ret=0;
int le=strlen(s);
for(int i=le-1;i>=0;i--){
ret=ret*base+s[i]-'a';
}
return ret;
}
bool match(char *s){
int le=strlen(s);
qu[le]=0;
for(int i=le-1;i>=0;i--){
qu[i]=qu[i+1]*base+(s[i]-'a'+last_ans)%26;
}
for(auto v:len){
int l=v.fr;
for(int i=0;i<le-l+1;i++){
ll tmp=qu[i]-qu[i+l]*Base[l];
if(S.find(tmp)!=S.end()) return 1;
}
}
return 0;
}
int main(){
Base[0]=1;
for(int i=1;i<N;i++) Base[i]=Base[i-1]*base;
int n=input(),q=input();
for(int i=0;i<n;i++){
scanf("%s",s);
p[i]=hsh(s);
lc[i]=strlen(s);
len[lc[i]]++;
S.insert(p[i]);
}
for(int i=0;i<q;i++){
int f=input();
if(f==1){
scanf("%s",s);
if(match(s)){
printf("YES\n");
last_ans=i;
}else{
printf("NO\n");
}
}else{
int pos=input(),alpha=input();
pos=(pos+last_ans)%n;
alpha=(alpha+last_ans)%26;
ll tmp=p[pos]+alpha*Base[lc[pos]];
S.erase(S.find(p[pos]));S.insert(p[pos]=tmp);
if(len[lc[pos]]==1) len.erase(lc[pos]);
else len[lc[pos]]--;
len[++lc[pos]]++;
}
}
}
温暖的签到题。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=105;
char s[maxn];
int main(){
int tt;
int i,n,m;
bool can;
scanf("%d",&tt);
while (tt--){
scanf("%s",s);
m=n=strlen(s);
while (!(m&1)) m/=2;
if (m!=1){
puts("NO");
continue;
}
can=true;
if (n==1){
puts("YES");
continue;
}
for (i=0;i<n;i+=2){
if (s[i]!='P'&&s[i+1]!='P')
can=false;
}
puts(can?"YES":"NO");
}
return 0;
}
题意:给定一个没有重边的图,求此图中一共有多少给定火柴人形状的子图。
题解:观察这个火柴人,我们发现七个点中,其他五个点都连在剩下的两个点上。因此,枚举中间相连的两个点,接下来分别判断它们分别是上半身和下半身中点的情况。
对于剩下所有的点,有四种情况:两个点都不连接,连接上半身的点,连接下半身的点,和两个都连接。
对于第一种情况,无需讨论。对于第二种情况,只要讨论下半身的剩下两个点在后两种情况中怎么取,就可以求出方案数。对所有方案数求和就是答案。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=205,mod=1e9+7;
int a[maxn][maxn];
int b[maxn];
ll c[maxn][maxn];
int n;
void sear(int u,int v,ll &cnt1,ll &cnt2,ll &cnt3){
int i;
cnt1=cnt2=cnt3=0;
memset(b,0,sizeof(b));
for (i=1;i<=n;i++) if (i!=u&&i!=v){
if (a[u][i]&&a[v][i]) cnt2++;
else if (a[u][i]) cnt1++;
else if (a[v][i]) cnt3++;
}
}
ll solve(ll x,ll y,ll z){
ll ans=0;
if (z>=2&&x+y>=3) ans=(ans+c[z][2]*c[x+y][3]%mod)%mod;
if (z>=1&&x+y>=4&&y>=1) ans=(ans+z*y%mod*c[x+y-1][3]%mod)%mod;
if (x+y>=5&&y>=2) ans=(ans+c[y][2]*c[x+y-2][3]%mod)%mod;
return ans;
}
int main(){
int i,j,m;
int u,v;
ll cnt1,cnt2,cnt3;
ll ans;
scanf("%d%d",&n,&m);
memset(c,0,sizeof(c));
for (i=0;i<=n;i++) c[i][0]=c[i][i]=1;
for (i=1;i<=n;i++) for (j=1;j<i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
memset(a,0,sizeof(a));
for (i=0;i<m;i++){
scanf("%d%d",&u,&v);
a[u][v]=1; a[v][u]=1;
}
ans=0;
for (i=1;i<=n;i++) for (j=1;j<=n;j++)
if (a[i][j]){
sear(i,j,cnt1,cnt2,cnt3);
ans+=solve(cnt1,cnt2,cnt3);
ans%=mod;
}
cout<<ans<<endl;
return 0;
}
题意:给出
个询问,每个询问给出
,求由多少个二元组
使得
题解:从
到
等曼哈顿距离为1的询问是可以
转移的,加上或者减去改变的数作为二元组其中一个点即可。然而四维还不能直接使用莫队,需要用容斥转化成二维查询。
表示
到
,
到
两个区间的询问,则
。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4+5;
typedef long long ll;
typedef long long LL;
struct query {
int l, r, ord, sgn;
} que[MAXN*4];
const int base=230;
bool operator < (query a,query b){
if (a.l/base!=b.l/base) return a.l/base<b.l/base;
if ((a.l/base)&1) return a.r<b.r;
else return a.r>b.r;
}
int ans_size;
ll ans[MAXN*4];
int n, m, a[MAXN];
vector<int> pos[MAXN];
LL calc(int x, int l, int r) {
int ll = lower_bound(pos[x].begin(), pos[x].end(), l) - pos[x].begin();
if (pos[x][ll] == n+1) return 0;
int rr = lower_bound(pos[x].begin(), pos[x].end(), r+1) - pos[x].begin() - 1;
if (rr < 0) return 0;
return rr-ll+1;
}
LL init(int l, int r) {
LL ans = 0;
for (int i=1; i<=n; ++i) {
ans += calc(i, 1, l) * calc(i, 1, r);
}
return ans;
}
LL addl(int l, int r) {
return calc(a[l+1], 1, r);
}
LL addr(int l, int r) {
return calc(a[r+1], 1, l);
}
LL minusl(int l, int r) {
return -calc(a[l], 1, r);
}
LL minusr(int l, int r) {
return -calc(a[r], 1, l);
}
void solve(){
int i,l,r;
ll anss;
sort(que,que+ans_size);
anss=init(1,1); l=r=1;
for (i=0;i<ans_size;i++){
while (r<que[i].r){
anss+=addr(l,r); r++;
}
while (l>que[i].l){
anss+=minusl(l,r); l--;
}
while (r>que[i].r){
anss+=minusr(l,r); r--;
}
while (l<que[i].l){
anss+=addl(l,r); l++;
}
ans[que[i].ord] += que[i].sgn*anss;
}
}
int main() {
// freopen("in.txt", "r", stdin);
scanf("%d", &n);
for (int i=1; i<=n; ++i) {
scanf("%d", &a[i]);
pos[a[i]].push_back(i);
}
for (int i=1; i<=n; ++i) {
pos[i].push_back(n+1);
}
scanf("%d", &m);
ans_size = 0;
for (int i=0; i<m; ++i) {
int l[2], r[2];
scanf("%d%d%d%d", &l[0], &r[0], &l[1], &r[1]);
que[ans_size++] = (query){r[0], r[1], i, 1};
que[ans_size++] = (query){l[0]-1, r[1], i, -1};
que[ans_size++] = (query){r[0], l[1]-1, i, -1};
que[ans_size++] = (query){l[0]-1, l[1]-1, i, 1};
}
solve();
for (int i=0; i<m; ++i) {
cout << ans[i] << endl;
}
return 0;
}
题意:给第一匹马找一个匹配,询问是否存在第一匹马的匹配代价大于其他所有的匹配。
题解:贪心。显然给第一匹马找最大的匹配。
其余的肯定是最大的和最小的匹配,依此类推。
直接排序,暴力判断即可。
#include<bits/stdc++.h>
using namespace std;
int T,n,m,w[100],h[100];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&w[i]);
for (int i=1;i<=n;i++)
scanf("%d",&h[i]);
sort(h+1,h+1+n,cmp);
sort(w+2,w+1+n);
int ans=h[1]*w[1];
for (int i=2;i<=n;i++)
if (h[i]*w[i]>=ans) ans=-1;
if (ans==-1) puts("NO");else puts("YES");
}
return 0;
}
题意:
,
;
。求第一个
满足
。
题解:
分别变成
可以在保证
不变的情况下,把
矫正成直线。题目变成询问
的前缀和第一个超过常数
的位置。
二分判断在哪一个周期超过了常数
,判断的方法是找一个周期的最高点。
对于第
个周期,前
个周期的前缀和可以直接得到,然后暴力计算本周期的前缀和,判断最大的是否超过了常数
。
对于第一个超过的周期,暴力寻找位置即可。
这道题目会爆long long,然后各种玄学的方法来调整判断,于是自闭了。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
int n;
LL m,a[100010],b[100010];
bool check(LL x) //x >=m
{
double y=0.0;
for (int i=1;i<=n;i++)
y+=(((double)a[i])+((double)i))*((double)x)+((double)x)*(((double)x)-1.0)/2.0*((double)n);
if (y>((double)m)*100000000.0) return true;
if (y<((double)m)*(-100000000.0)) return false;
LL ans=0;
for (int i=1;i<=n;i++)
{
if (((double)a[i])+((double)i)+((double)(n)*(double)(x))>((double)m)*100000000.0) return true;
if (((double)a[i])+((double)i)+((double)(n)*(double)(x))<((double)m)*(-100000000.0)) return false;
b[i]=(a[i]+((LL)i)+((LL)(n)*(x)));
ans+=(a[i]+((LL)i))*x+x*(x-1LL)/2LL*(LL)n;
}
for (int i=1;i<=n;i++)
{
if (((double)b[i])+((double)ans)>((double)m)*100000000.0) return true;
if (((double)b[i])+((double)ans)<((double)m)*(-100000000.0)) return false;
if (b[i]+ans>=m) return true;
else ans+=b[i];
}
return false;
}
LL solve()
{
LL ans=0,res=m;
for (int i=1;i<=500*n;i++)
{
ans+=a[(i-1)%n+1];
res-=(LL)i;
if (ans>=res) return (LL)i;
}
return -1;
}
int main()
{
scanf("%d%I64d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%I64d",&a[i]);
LL x=solve();
if (x!=-1)
{
printf("%I64d\n",x);
return 0;
}
LL l=0,r=300000000000LL,mid,res;
while(l<=r)
{
mid=l+r>>1;
if (check(mid)) res=mid,r=mid-1;
else l=mid+1;
}
LL ans=res*n,s=0;
for (int i=1;i<=n;i++)
s+=(a[i]+((LL)i))*res+res*(res-1LL)/2LL*(LL)n;
if (s>=m) {printf("%I64d\n",ans);return 0;}
//cout<<res<<" "<<s<<endl;
for (int i=1;i<=n;i++)
{
a[i]=(a[i]+((LL)i)+((LL)(n)*(res)));
ans++;s+=a[i];
if (s>=m) break;
}
printf("%I64d\n",ans);
return 0;
}
题意:给出两个素数
(
),求出只包含加减运算的的运算步骤,且中间值和加或减的数均为素数。
题解:奇数加奇数为偶数,而只有2不是奇数,所以运算的情况是相当少的。同时一个数最多加2两次,否则
模3的值均不同,有一个一定不是素数。如果一个数是奇数,则它只能加减2,或者是减到2。如果一个数是2,则它可以加或减到b-4~b+4。判素数应该使用Miller-Rabin,由于之前没怎么用过就被红书的板子坑了(大概是素数没选对,数据会卡。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
typedef long long LL;
LL a, b;
const LL m=7, aa[m]={2, 3, 5, 7, 11, 13, 17};
LL n, p;
LL fmul(LL a, LL b, LL p){ //将b分解为二进制,返回a*b%p
LL ans=0;
for (; b; b>>=1, a+=a, a%=p)
if (b&1) ans+=a, ans%=p;
return ans;
}
LL fpow(LL a, LL x, LL p){
LL ans=1, base=a;
for (; x; x>>=1, base=fmul(base, base, p))
if (x&1) ans=fmul(ans, base, p);
return ans;
}
bool MR(LL a, LL x, LL p){
LL t=fpow(a, x, p);
if (t!=1&&t!=p-1) return false;
if (t==1&&x&1||t==p-1) return true;
return MR(a, x>>1, p);
}
bool isPrime(LL p){
if (p < 2) return false;
if (p == 2) return true;
if (p&1==0) return false;
for (LL i=0; i<m; ++i){
if (p==aa[i]) return true;
if (fpow(aa[i], p-1, p)!=1) return false;
if (!MR(aa[i], (p-1)>>1, p)) return false;
}
return true;
}
struct node {
int fa, step;
LL v;
node(int fa, LL v, int step):fa(fa), v(v), step(step){}
node(){}
} que[MAXN];
int st, ed;
vector<LL> ans;
map<LL, int> mp;
bool valid(LL v, int step) {
if (!mp.count(v) || mp[v] >= step) {
return true;
}
return false;
}
int bfs(LL s, LL t) {
st = ed = 0;
que[ed++] = node(-1, s, 0);
int found = -1;
mp.clear();
mp[s] = 0;
while (st < ed) {
node now = que[st];
if (found != -1 && now.step > found) return 1;
if (now.v == t) {
if (found == now.step) return -1;
found = now.step;
int id = st;
while (id != -1) {
ans.push_back(que[id].v);
id = que[id].fa;
}
++st;
continue;
}
if (now.v % 2) {
LL nextv = now.v+2;
if (valid(nextv, now.step+1) && isPrime(nextv)) {
mp[nextv] = now.step+1;
que[ed++] = node(st, nextv, now.step+1);
}
nextv = now.v-2;
if (valid(nextv, now.step+1) && isPrime(nextv)) {
que[ed++] = node(st, nextv, now.step+1);
mp[nextv] = now.step+1;
}
} else {
for (LL j=t-4; j<=t+4; j+=2) {
if (valid(j, now.step+1) && isPrime(j) && (isPrime(j-now.v) || isPrime(now.v-j))) {
mp[j] = now.step+1;
que[ed++] = node(st, j, now.step+1);
}
}
}
if (valid(2, now.step+1) && isPrime(now.v-2)) {
mp[2] = now.step+1;
que[ed++] = node(st, 2, now.step+1);
}
st++;
}
if (found != -1) return 1;
else return 0;
}
int main() {
cin >> a >> b;
int suc = bfs(a, b);
if (suc == 1) {
int sz = ans.size();
printf("%I64d", ans[sz-1]);
for (int i=sz-2; i>=0; --i) {
printf("->%I64d",ans[i]);
}
putchar('\n');
} else if (suc == 0) {
puts("Unlucky Benny");
} else puts("Poor Benny");
return 0;
}
题意:给定一棵树,每一个节点上有一个或正或负权值,现在每次访问两个节点,问这两个节点路径上的点权和最大的非空子路径的点权和是多少。
题解:
。用倍增法维护并合并一条竖直方向路径的三个元素:含有顶节点的最大子路径点权和,含有底节点的最大子路径点权和,和普通的最大子路径点权和,最后再合并两条从访问节点出发到其
的向上路径。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const long long inf = 1e18;
int n, Q, u, v;
long long a[maxn];
struct Edge {int to, nex;} edge[maxn << 1];
int head[maxn], ecnt;
void add_edge (int u, int v) {edge[++ecnt] = {v, head[u]}; head[u] = ecnt;}
int father[maxn], hson[maxn], siz[maxn], depth[maxn];
int cnt, dfn[maxn], rk[maxn], top[maxn];
#define ls rt << 1
#define rs rt << 1 | 1
struct node {long long sum, pre, suf, maxsum;} tr[maxn << 2], p[maxn], None = {0, -inf, -inf, -inf};
node operator + (node a, node b){
return{
a.sum + b.sum,
max (a.pre, a.sum + b.pre),
max (a.suf + b.sum, b.suf),
max (a.suf + b.pre, max (a.maxsum, b.maxsum))
};
}
void build (int rt, int l, int r)
{
if (l == r) {tr[rt] = {a[rk[l]], a[rk[l]], a[rk[l]], a[rk[l]]}; return;}
int mid = (l + r) >> 1;
build (ls, l, mid);
build (rs, mid + 1, r);
tr[rt] = tr[ls] + tr[rs];
}
node query (int nl, int nr, int l = 1, int r = n, int rt = 1)
{
if (nl > r || nr < l) return None;
if (nl <= l && nr >= r) return tr[rt];
int mid = (l + r) >> 1;
node ret = query(nl, nr, l, mid, ls) + query(nl, nr, mid + 1, r, rs);
return ret;
}
void get_hson (int now, int fa)
{
father[now] = fa;
siz[now] = 1;
depth[now] = depth[fa] + 1;
int it = 0;
for (int i = head[now]; i; i = edge[i].nex)
{
int to = edge[i].to;
if (to == fa) continue;
get_hson (to, now);
siz[now] += siz[to];
if (siz[to] > siz[it]) {hson[now] = to; it = to;}
}
}
void dfs (int now, int thetop)
{
top[now] = thetop;
dfn[now] = ++cnt;
rk[dfn[now]] = now;
if (siz[now] == 1) return;
dfs (hson[now], thetop);
for (int i = head[now]; i; i = edge[i].nex)
{
int to = edge[i].to;
if (to == father[now] || to == hson[now]) continue;
dfs (to, to);
}
}
long long path_max (int u, int v)
{
node nou = None, nov = None;
while (top[u] != top[v])
{
if (depth[top[u]] < depth[top[v]]) {swap (u, v); swap(nov, nou);}
nou = p[u] + nou;
u = father[top[u]];
}
if (depth[u] > depth[v]) {swap (u, v); swap(nou, nov);}
nov = query(dfn[u], dfn[v]) + nov;
long long ret = max (max (nou.maxsum, nov.maxsum), nou.pre + nov.pre);
return ret;
}
int main()
{
//freopen("C:/Users/MACHENIKE/Desktop/data.in","r",stdin);
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
scanf("%d %d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
get_hson(1, 0);
dfs(1, 1);
for (int i = 1; i <= n; i++) scanf("%lld", a + i);
build(1, 1, n);
for (int i = 1; i <= n; i++) p[i] = query(dfn[top[i]], dfn[i]);
scanf("%d", &Q);
while (Q--)
{
scanf("%d %d", &u, &v);
printf("%lld\n", path_max(u, v));
}
return 0;
}
题意:有一列长度为
的火车,求一共有多少种
个颜色的染色方案,使得恰好有
种方案选出长度为
的颜色相同的一段车厢。
题解:首先,我们发现,如果一共有
段相同颜色段,一个染色方案的选出车厢的方案数为
。
我们设
代表第
个车厢结尾有
种方案选出的染色数,我们发现,除了只有一段的情况,
。我们发现,这是一段折线段,而拐点所在列是
。因此,我们每次处理一列
,之后将拐点列上的
元素从平线加到斜线上,即可在
的时间内求出答案。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=4e3+5;
const ll mod=1e9+7;
ll dp[maxn][maxn];
ll sum1[maxn],sum2[maxn];
int main(){
int i,j,n,d,t,k;
ll ans;
scanf("%d%d%d%d",&n,&d,&t,&k);
memset(dp,0,sizeof(dp));
memset(sum1,0,sizeof(sum2));
memset(sum2,0,sizeof(sum2));
for (i=1;i<=n;i++){
for (j=0;j<=t;j++){
if (j==max(i-d+1,0)) dp[i][j]+=k;
dp[i][j]+=sum1[j]*(k-1)%mod;
if (i-j-d+1>=0) dp[i][j]+=sum2[i-d-j+1]*(k-1)%mod;
dp[i][j]%=mod;
sum1[j]=(sum1[j]+dp[i][j])%mod;
if (i-d+1>=0) sum1[j]=(sum1[j]-dp[i-d+1][j])%mod;
if (i-d-j+1>=0) sum2[i-d-j+1]=(sum2[i-d-j+1]+dp[i-d+1][j])%mod;
}
}
cout<<((dp[n][t]+mod)%mod+mod)%mod<<endl;
return 0;
}