反思
- 第二遍了，一定要看数据范围……
题目简述
T1 老光棍
可以(hash)一波带走，复杂度是(O(Tn))的
注意：多解的情况是“不同的字符串(A)”，所以在增加答案的时候需要特别判断其和原来的答案是否相同
code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 2000005
ll T,n;
char s[N];
bool vis[30],flag;
ll ans=0,pos;
const ull base=31;
ull hash[N],po[N];
void pp()
{
po[0]=1;
for(int i=1;i<=N;i++)po[i]=po[i-1]*base;
}
void gethash()
{
memset(hash,0,sizeof hash);
hash[0]=0;
for(int i=1;i<=n;i++)
{
hash[i]=hash[i-1]*base+(s[i]-'A');
}
}
ull get(ll l,ll r)
{
if(l>r)return 0;
return hash[r]-hash[l-1]*po[r-l+1];
}
ull tmp;
int main()
{
//freopen("owo.in","r",stdin);
scanf("%lld",&T);
pp();
while(T--)
{
scanf("%lld",&n);
scanf("%s",s+1);
if(n%2==0)
{
puts("NOT POSSIBLE");
continue;
}
gethash();
ll t=(n+1)/2;
ans=0;
tmp=-1;
//cout<<endl;
for(int i=1;i<=t;i++)
{
//cout<<1<<' '<<i-1<<' '<<i+1<<' '<<t<<' '<<t+1<<' '<<t+i-1<<' '<<t+i<<' '<<n<<endl;
//cout<<get(1,i-1)<<' '<<get(t+1,t+i-1)<<' '<<get(i+1,t)<<' '<<get(t+i,n)<<endl;
if(get(1,i-1)==get(t+1,t+i-1)&&get(i+1,t)==get(t+i,n))
{
if(get(t+1,n)!=tmp)ans++;
tmp=get(t+1,n);
pos=i;
//cout<<pos<<endl;
}
}
for(int i=t+1;i<=n;i++)
{
//cout<<get(1,i-t)<<' '<<get(t,i-1)<<' '<<get(i-t+1,t-1)<<' '<<get(i+1,n)<<endl;
if(get(1,i-t)==get(t,i-1)&&get(i-t+1,t-1)==get(i+1,n))
{
if(get(1,t-1)!=tmp)ans++;
tmp=get(1,t-1);
pos=i;
//cout<<pos<<endl;
}
}
if(ans>1)
{
puts("NOT UNIQUE");
}
else if(ans==0)
{
puts("NOT POSSIBLE");
}
else
{
if(pos<=t)
{
for(int i=t+1;i<=n;i++)putchar(s[i]);
}
else
{
for(int i=1;i<=t-1;i++)putchar(s[i]);
}
puts("");
}
}
return 0;
}
T2 渔船
网络流？三分？在补了在补了……
（然而还并不知道网络流为何物
（可能不久会放上来……
T3 马克的达人秀
原题luoguP4377 Talent Show
01分数规划：洛谷日报(#121)
01分数规划+01背包(
ightarrow)最优比率背包
code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 255
#define T 250005
ll n,ww;
ll t[N],w[N];
ll sum=0;
ll f[T];
bool work(ll x)
{
memset(f,128,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=ww;j>=0;j--)
{
f[min(j+w[i],ww)]=max(f[min(j+w[i],ww)],f[j]+t[i]-x*w[i]);
}
}
return f[ww]>=0;
}
int main()
{
//freopen("owo.in","r",stdin);
//freopen("awa.out","w",stdout);
scanf("%lld%lld",&n,&ww);
for(int i=1;i<=n;i++)scanf("%lld%lld",&w[i],&t[i]),t[i]*=1000;
ll l=0,r=10000000,m;
while(l<r)
{
m=(l+r)>>1;
//cout<<m<<endl;
if(work(m))l=m+1;
else r=m;
}
printf("%lld",l-1);
return 0;
}
T4 爬山
一个比较有用的结论：
给定一组数据，用猜来的平均值计算他的方差，计算结果一定(geq)正确结果
推柿子：（by yspm
(设数据(x_1dots x_n)已经给定，猜的平均数为(ar{x})，为了方便，所有的(sumlimits^{n}_{i=1})简写为(sum)
[egin{aligned}
s^2&=frac{sum(x_i-ar{x})^2}{n}\
&=frac{sum(x_i^2)-2sum(x_iar{x})+sum(ar{x}^2)}{n}\
frac{sum(x_i^2)}{n}是定值，去掉\
&=frac{sum(ar{x}^2)-2sum(x_iar{x})}{n}\
&=ar{x}^2-frac{2sum(x_iar{x})}{n}\
&=ar{x}^2-frac{2ar{x}sum x_i}{n}\
配方得\
&=(ar{x}-frac{sum x_i}{n})^2-(frac{sum x_i}{n})^2\
当且仅当取ar{x}=frac{sum x_i}{n}时，取最小值\
其中frac{sum x_i}{n}即为正确的平均数\
end{aligned}]
所以，可以枚举每个点到终点的路径长度与经过的点数，从而得到这条路径的平均值，用这个“猜到”的平均值计算到终点的最小方差，取所有这些答案里的最小值就是正确答案
另外有向无环图可以用拓扑排序帮助求最短路
code：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define E 2005
#define N 55
#define inf 10000000000000000
struct edge
{
ll u,v,w;
}e[E];
ll head[E],next[E],tot=0;
void add(ll a,ll b,ll c)
{
++tot;
e[tot].u=a;
e[tot].v=b;
e[tot].w=c;
next[tot]=head[a];
head[a]=tot;
}
ll n,m,a,b,c;
ll in[N],tmp[N];
double ans=1e16;
queue<ll> q;
ll mi[N][25],mx[N][25];
db dis[N][25];
int main()
{
//freopen("owo.in","r",stdin);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&a,&b,&c);
add(a,b,c);
in[b]++;
}
while(!q.empty())q.pop();
memcpy(tmp,in,sizeof in);
for(int i=1;i<=n;i++)if(!tmp[i])q.push(i);
for(int i=1;i<=n;i++)for(int j=0;j<=20;j++)mi[i][j]=inf,mx[i][j]=-inf;
mi[1][0]=mx[1][0]=0;
while(!q.empty())
{
ll u=q.front();
//cout<<u<<endl;
q.pop();
for(int i=head[u];i;i=next[i])
{
ll v=e[i].v;
for(int j=0;j<=19;j++)
{
if(mi[u][j]!=inf)
{
mi[v][j+1]=min(mi[v][j+1],mi[u][j]+e[i].w);
mx[v][j+1]=max(mx[v][j+1],mx[u][j]+e[i].w);
//cout<<mi[v][j+1]<<' '<<mx[v][j+1]<<endl;
}
}
}
for(int i=head[u];i;i=next[i])
{
ll v=e[i].v;
if(--tmp[v]==0)q.push(v);
}
}
for(int i=1;i<=19;i++)
{
//cout<<mi[n][i]<<endl;
if(mi[n][i]==inf)continue;
for(int j=mi[n][i];j<=mx[n][i];j++)
{
db avg=(db)j/(db)i;
//cout<<avg<<endl;
memcpy(tmp,in,sizeof in);
for(int k=1;k<=n;k++)for(int l=0;l<=19;l++)dis[k][l]=inf;
dis[1][0]=0;
while(!q.empty())q.pop();
for(int k=1;k<=n;k++)if(!tmp[k])q.push(k);
while(!q.empty())
{
ll u=q.front();
q.pop();
//cout<<u<<endl;
for(int k=0;k<i;k++)
{
if(dis[u][k]==inf)continue;
for(int l=head[u];l;l=next[l])
{
ll v=e[l].v,w=e[l].w;
dis[v][k+1]=min(dis[v][k+1],dis[u][k]+((db)w-avg)*((db)w-avg));
}
}
for(int k=head[u];k;k=next[k])
{
ll v=e[k].v;
if(--tmp[v]==0)q.push(v);
}
}
//cout<<dis[n][i]<<endl;
ans=min(ans,dis[n][i]/(db)i);
}
}
printf("%.4lf",ans);
return 0;
}