2017新年做题记 - cool's Blog
2017新年做题记
竟然已经2017年了，停课已经快1个月了，但是还是没有很强的鏼题能力，好惨。
[CF750E]给定一个串，求最少移去多少的字符才能使某个子串含有子序列2017不含有子序列2016
考虑暴力，总共有5个状态。
0->啥都没有 1->只有2 2->只有20 3->只有201 4->只有2017
然后可以O（n）转移。经过lbn的指导，可以把这个dp方程变成矩阵，然后只要求一段区间的矩阵和即可。
//world happy new year
#include <cstdio>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define N 550000
#define M 200010
#define inf 100000000
char s[M];
int n,q,x,y;
struct xfy
{
int a[5][5];
void reset()
{
rep(i,0,4) rep(j,0,4) a[i][j] = inf;
rep(i,0,4) a[i][i] = 0;
}
void init(int x)
{
reset();
if (x == 2) a[0][0] = 1, a[0][1] = 0;
else if (x == 0) a[1][1] = 1, a[1][2] = 0;
else if (x == 1) a[2][2] = 1, a[2][3] = 0;
else if (x == 6) a[3][3] = 1, a[4][4] = 1;
else if (x == 7) a[3][3] = 1, a[3][4] = 0;
}
}dp[N],ans;
void checkmin(int& x,int y)
{
if (x > y) x = y;
}
xfy operator +(xfy x,xfy y)
{
xfy c;
rep(i,0,4) rep(j,0,4)
{
c.a[i][j] = inf;
rep(k,0,4) checkmin(c.a[i][j],x.a[i][k]+y.a[k][j]);
}
return c;
}
#define lson l,mid,k<<1
#define rson mid+1,r,k<<1|1
void Build(int l,int r,int k)
{
if (l == r)
{
dp[k].init(s[l]-'0');
return;
}
int mid = l+r>>1;
Build(lson); Build(rson);
dp[k] = dp[k<<1]+dp[k<<1|1];
}
void query(int L,int R,int l,int r,int k)
{
if (L <= l && r <= R)
{
ans = ans+dp[k];
return;
}
int mid = l+r>>1;
if (L <= mid) query(L,R,lson);
if (R > mid) query(L,R,rson);
}
int main()
{
scanf("%d%d%s",&n,&q,s+1);
Build(1,n,1);
for (;q--;)
{
scanf("%d%d",&x,&y);
ans.reset();
query(x,y,1,n,1);
if (ans.a[0][4] > n) puts("-1");
else printf("%d\n",ans.a[0][4]);
}
return 0;
}
[CF749E]对于一个1-n的全排列，随机选择一个区间并random_shuffle，求一次操作后的期望逆序对数。
首先一个长度为k的序列，打乱后的期望逆序对为k*(k-1)/4
那么现在只要求出每个区间的逆序对和即可。
考虑ans[i]为所有已i的开始的区间的逆序对和，如果已知ans[i+1]，那么第i+1~n个数中每个数被计算的次数要么是0，要么是n-j+1，所以用树状数组维护即可，每次add(a[i],n-i+1)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 100010
double ans1,ans2,tmp,S;
int a[N],n;
ll g[N];
void add(int x,int y)
{
for (;x <= n;x += x&-x)
g[x] += y;
}
ll query(int x)
{
ll y = 0;
for (;x;x -= x&-x)
y += g[x];
return y;
}
int main()
{
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]);
drep(i,n,1)
{
ans1 += (double)query(a[i]);
add(a[i],1);
}
clr(g,0);
drep(i,n,1)
{
ans2 -= (double)query(a[i])*i;
add(a[i],n-i+1);
}
rep(i,1,n)
{
tmp += (double)(i-1)/2.0;
ans2 += (double)tmp*(n-i+1);
}
printf("%.10f",ans1+2.0*ans2/n/(n+1));
return 0;
}
[CF735E]给一棵树黑白染色，要求每个点离最近的黑色点的距离<=k，求方案数。（n<=100,k<=20）
不是很懂这个数据，感觉是nk^2的。dp[0][n][i]表示符合条件的情况下，最近的黑点距自己i。
dp[1][n][i]表示符合条件的情况下，最远的不符合的点距自己i。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 110
int h[N<<1],last[N<<1],head[N],l;
int n,k,x,y,f[2][N][25],f0[25],f1[25],ans;
void Add(int& x,int y)
{
x += y;
if (x >= zhl) x -= zhl;
if (x < 0) x += zhl;
}
void add(int x,int y)
{
h[++l] = y;
last[l] = head[x];
head[x] = l;
}
void dfs(int x,int fa)
{
f[0][x][0] = f[1][x][0] = 1;
for (int i = head[x],y;i;i = last[i])
{
if ((y=h[i]) == fa) continue;
dfs(y,x); clr(f0,0); clr(f1,0);
rep(w,0,k) rep(j,0,k) Add(f0[min(w,j+1)],(ll)f[0][x][w]*f[0][y][j]%zhl);
rep(w,0,k) rep(j,0,k) if (w+j+1 <= k) Add(f0[w],(ll)f[0][x][w]*f[1][y][j]%zhl);
else Add(f1[j+1],(ll)f[0][x][w]*f[1][y][j]%zhl);
rep(w,0,k) rep(j,0,k) if (w+j+1 <= k) Add(f0[j+1],(ll)f[1][x][w]*f[0][y][j]%zhl);
else Add(f1[w],(ll)f[1][x][w]*f[0][y][j]%zhl);
rep(w,0,k) rep(j,0,k) Add(f1[max(w,j+1)],(ll)f[1][x][w]*f[1][y][j]%zhl);
memcpy(f[0][x],f0,sizeof(f0));
memcpy(f[1][x],f1,sizeof(f1));
}
}
int main()
{
scanf("%d%d",&n,&k);
rep(i,2,n)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0);
rep(i,0,k) Add(ans,f[0][1][i]);
printf("%d",ans);
return 0;
}
[bzoj3513]n个ai的木棍，求选出三根不能拼成三角形的概率。ai<=1e6
做的第一道fft优化dp，裸题。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
const double pi=3.141592653589793238462643383279502884197169399375105820974944;
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define NN 400010
struct E
{
double r,i;
E(double _r=0,double _i=0): r(_r),i(_i){}
E operator+(E x){return E(r+x.r,i+x.i);}
E operator-(E x){return E(r-x.r,i-x.i);}
E operator*(E x){return E(r*x.r-i*x.i,r*x.i+i*x.r);}
}a[NN],b[NN],c[NN];
int n,m,L,R[NN],s[NN],T,mx,N,x;
ll ans,tot,sum;
void fft(E *a,int f,int n)
{
rep(i,0,n-1) if(i<R[i]) swap(a[i],a[R[i]]);
for(int i=1;i<n;i<<=1)
{
E wn(cos(pi/i),f*sin(pi/i));
for(int j=0;j<n;j+=(i<<1))
{
E w(1,0);
for(int k=0;k<i;k++,w=w*wn)
{
E x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y;a[j+k+i]=x-y;
}
}
}
if(f==-1) rep(i,0,n-1) a[i].r/=n;
}
int main()
{
for (scanf("%d",&T);T--;)
{
scanf("%d",&n); mx = 0; clr(s,0);
rep(i,1,n) scanf("%d",&x),s[x]++,mx = max(mx,x);
for (N=1,L=0;N<mx+1;N<<=1,L++);
N<<=1; L++; mx++; clr(R,0);
rep(i,0,N-1) R[i] = (R[i>>1]>>1)|((i&1)<<(L-1));
rep(i,0,N-1) a[i] = b[i] = E((double)s[i]);
fft(a,1,N); fft(b,1,N);
rep(i,0,N-1) c[i] = a[i]*b[i];
fft(c,-1,N);
ans=0,tot=1LL*n*(n-1)*(n-2)/6,sum=0;
rep(i,0,mx)
{
sum+=(ll)(c[i].r+0.5);
if (i%2==0) sum-=s[i/2];
if (!s[i]) continue;
ans+=1LL*sum*s[i];
}
ans/=2;
printf("%.7lf\n",1.0-(double)ans/tot);
}
return 0;
}
[CF739E]好神的题目，还没有完全理解这个做法。
f[i][j][k]=max(f[i-1][j][k],f[i-1][j-1][k]+p[i],f[i-1][j][k-1]+u[i],f[i-1][j-1][k-1]+t[i])
t[i]=1-(1-u[i])(1-p[i])
这样是O(n^3)的
f[i][j][k]是一个关于k单调的凸函数，我们假定一个常数S，那么f[i][j][k]-S*k一定是一个凸函数，设其极值点为x0.
那么f[n][a]的极值点是可以通过O（n^2）的，如果极值点为b那么f[n][a][b]+S*b就是答案，然后二分S即可。
感觉整个过程，就是通过max传递极值点的性质来做的。撕烤一下如何举一反三。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define rep(i,a,b) for (int i = a;i <= b;i++)
#define drep(i,a,b) for (int i = a;i >= b;i--)
#define ist insert
#define ers erase
#define clr(a,b) memset(a,b,sizeof a)
#define ll long long
#define inf 1000000000
#define zhl 1000000007
#define eps 1e-9
template<class T>void Swap(T &a,T &b){ T c = a;a = b;b = c; }
template<class T>T max(T& a,T& b){ return a<b?b:a; }
template<class T>T min(T& a,T& b){ return a>b?b:a; }
using namespace std;
#define N 2010
int n,a,b;
double p[N],u[N],t[N],f[N][N],g[N][N],l,r;
double slop(double K)
{
double f1,g1;
rep(i,1,n) rep(j,0,a)
{
f1 = g1 = 0;
if (f[i-1][j] > f1+eps) f1 = f[i-1][j],g1 = g[i-1][j];
if (f[i-1][j]-K+u[i] > f1+eps) f1 = f[i-1][j]-K+u[i],g1 = g[i-1][j]+1;
if (j && f[i-1][j-1]+p[i] > f1+eps) f1 = f[i-1][j-1]+p[i],g1 = g[i-1][j-1];
if (j && f[i-1][j-1]+t[i]-K > f1+eps) f1 = f[i-1][j-1]+t[i]-K,g1 = g[i-1][j-1]+1;
f[i][j] = f1; g[i][j] = g1;
}
return g[n][a];
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
rep(i,1,n) scanf("%lf",&p[i]);
rep(i,1,n) scanf("%lf",&u[i]);
rep(i,1,n) t[i] = 1.0-(1.0-p[i])*(1.0-u[i]);
for (l = -2000,r = 2000;r-l>eps;)
{
double mid = (l+r)*0.5;
if (slop(mid)<b) r = mid;
else l = mid;
}
printf("%.5lf",f[n][a]+l*b);
return 0;
}
2022年8月09日 20:00
Well, to be precise it is very important for anything to run properly such as a business creative which is grammar perfect or else a news outlet or a blog article which is properly checked for any grammar mistakes. Grammarly Alternative At the same time, people love to believe that working knowledge of grammar better resides with humans but it is true that the modern softwares, tools and plugins like Grammarly has been a great help to anyone who is looking to ensure that their words make sense.
2022年8月20日 20:26
Argos doesn't currently offer a student discount, however they offer year round sales both online and in store, argos sale and you can also find great discount vouchers online. Keep an eye on this website for the latest deals we find so you can get yourself a bargain. student discount card and app giving you access to huge offers on food and essentials, tech, travel and home delivery.