每次开一个坑都像是重新被碾压的预感
最近的新闻，以前很喜欢乔任梁的《复活》。。。然后他就死了。。。感觉我再多愁善感一点的话。。。就要悲伤逆流成河了吧。。。
Contest 09/24（乐滋滋的场，良心场）100+100+0
T1：这题做得很羞愧。。。因为我根本证不出那个结论。。猜的。。
T2：这题做得很羞愧。。。因为听到了隔壁GG讲了伸头缩尾法。。。
T3：因为少了一个半小时就没交。yy了一个跟正解差不多的想法。。。只是把枚举K去掉了，但是这样就MLE了。。。我口胡一下。。不写了因为懒得评测。。。
Contest 09/25（小火车的场，233）70+10+0
T1：A了一片。。。。。撞墙了。。。。不会找规律。。。不会推推推。。。。把一秒续到两秒，把一个单位续到两个，发现每一秒的行动概率都是一半，而且还不用停，直接算出往左t-p，往右t-p，C（）一下就好了。。。。我口胡一下。。不写了因为懒得评测。。。
T2：一道很滑稽的树形DP。当时在yy自己的一个二分图，居然真的得分了。先想一个n三次做法，f[i,j,k]表示i统治的联通块中，最大为j，最小为k，最少操作次数，优化到最好差不多可以拿60分。可以削去一维，f[i][j]表示i为根的联通块内最小值不小于j的次数，g[i]表示min{f[i][j],v[i]-d<=j<=v[i]+d}.
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200000
#define M 5050
#define ll long long
using namespace std;
,edgenew=,d,yes,ans,lu,n;
int fa[M],bian[M][M],a[M],ru[N];
int head[N],next[N],vet[N];
ll f[M][M],g[M];
ll min(ll a,ll b){
if(a<b)return a;else return b;
}
void add(int u,int v){
edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;
}
void dfs(int u,int ff){
int e=head[u];
){
int v=vet[e];
if(v!=ff){
dfs(v,u);
}
e=next[e];
}
){
g[u]=;
for(int j=a[u]-d;j<=a[u];j++){
)continue;
f[u][j]=;
}return;
}
for(int j=a[u]-d;j<=a[u];j++){
)continue;
e=head[u];f[u][j]=;
){
int v=vet[e];
if(v!=ff){
f[u][j]+=min(f[v][j]-,g[v]);
}
e=next[e];
}
}
;i<=a[u];i++)g[u]=min(g[u],f[u][i]);//printf("%d %lld\n",u,g[u]);
}
int main()
{
freopen("yi.in","r",stdin);//freopen("yi.out","w",stdout);
scanf("%d%d",&d,&n);
;i<=n;i++)scanf("%d",&a[i]);
;i<=n-;i++){
int u,v;
scanf("%d%d",&u,&v);add(u,v);add(v,u);ru[u]++;ru[v]++;
}
memset(g,,,sizeof(f));
dfs(,);
printf(]);
fclose(stdin);fclose(stdout);
}
T3：省选难度.暴力写挂.部分一和部分二都要可持久化左偏树,标算则转化成了对偶图的K长路问题（董宏华）。。这次连口胡都做不到了。。。
WZMSday1:
因为温州场虽然是后考，但是印象比较深刻。就先拿来订正一下。
T1：一个结论。可以通过暴力的方式求得。
T2：算C（）的过程中少了几个质数，还好才wa了一半的点。
T3：通过题解的idea知道，大于根号n的质数不会互相影响，所以需要枚举的的小于根号n的质数只有11个。不过不要忘记把所有质数从小到大排序一下orz。
WZMSday2：
T1：用小学奥数姿势就好了。题解中给出了组合数学的办法orz。
T2：一个树形DP。交了一个n方做法本来以为只能拿50分。若是再多想几步可以发现，如果将根移换到相邻的位置，实际只改变两个点的dp值。这里需要极其恶心的讨论，改了半个小时。。。。记了最大，次大，最小，次小，还记录了最值所在位置。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 600010
using namespace std;
int n,edgenum;
ll a[N],a2[N],b2[N],b[N],ans[N];
int head[N],next[N],vet[N],pri[N],f1[N],g1[N];
ll max(ll a,ll b){
if(a>b)return a;else return b;
}
ll min(ll a,ll b){
if(a<b)return a;else return b;
}
void add(int u,int v,int w){
edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;
pri[edgenum]=w;
}
void dfs(int u,int ff){
;b2[u]=b[u]=;
){
int v=vet[e];
if(v!=ff){
dfs(v,u);
if(b[v]+pri[e]>=a[u])a2[u]=a[u],a[u]=b[v]+pri[e],f1[u]=v;else if
(b[v]+pri[e]>=a2[u])a2[u]=b[v]+pri[e];
if(a[v]+pri[e]<=b[u])b2[u]=b[u],b[u]=a[v]+pri[e],g1[u]=v;else if
(a[v]+pri[e]<=b2[u])b2[u]=a[v]+pri[e];
}
e=next[e];
}
)b[u]=;
}
void find(int u,int ff){
int e=head[u];ans[u]=a[u];
){
int v=vet[e];
if(v!=ff){
b[v]=min(b[v],pri[e]+a[u]);
if(g1[u]!=v){
if(pri[e]+b[u]>=a[v]){
a2[v]=a[v];a[v]=pri[e]+b[u];f1[v]=u;
}else if(pri[e]+b[u]>=a2[v]){
a2[v]=pri[e]+b[u];
}
}else {
if(pri[e]+b2[u]>=a[v]){
a2[v]=a[v];a[v]=pri[e]+b2[u];f1[v]=u;
}else if(pri[e]+b2[u]>=a2[v]){
a2[v]=pri[e]+b2[u];
}
}
if(f1[u]!=v){
if(pri[e]+a[u]<=b[v]){
b2[v]=b[v];b[v]=pri[e]+a[u];g1[v]=u;
}else if(pri[e]+a[u]<=b2[v]){
b2[v]=pri[e]+a[u];
}
}else {
if(pri[e]+a2[u]<=b[v]){
b2[v]=b[v];b[v]=pri[e]+a2[u];g1[v]=u;
}else if(pri[e]+a2[u]<=b2[v]){
b2[v]=pri[e]+a2[u];
}
}
find(v,u);
}
e=next[e];
}
}
int main()
{
freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);
scanf("%d",&n);
;i<=n-;i++){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
add(u,v,c);add(v,u,c);
}
dfs(,);
//for(int i=1;i<=n;i++)printf("====%lld\n",a[i]);
find(,);
;i<=n;i++){
printf("%lld\n",ans[i]);
}
fclose(stdin);fclose(stdout);
}
travel
T3 : 外向环套树。被虐哭了。。。TAT
第二场day1：
T1：《溢出》没有赶上这场。。。也不知道是哪所学校出的。T1写得要吐血。。。。我发现我对于C++的编译细节简直一窍不通。。。简直了。。。。。。小数的误差范围会达到1，对于比较大的数之后一定要加上ull。。。。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ull double
#define ul unsigned long long
#define N 1000000
using namespace std;
int ans,now;
ull all;
unsigned long long va,maxn;
char str[N],sta[N];
int main()
{
freopen("overflow.in","r",stdin);freopen("overflow.out","w",stdout);
int cas;
scanf("%d",&cas);all=1.0;
ans=-;now=;unsigned ;;
){;k--;sta[k]=;}
)!=EOF){
//printf("all===%.2lf\n",all);
]==]=='u'){
){
)printf("never\n");else printf("%d\n",ans);
}
]=='i'){
]==;
]==;
]==')maxn=2147483647ull;
]==')maxn=9223372036854775807ull;
}
]=='u'){
scanf();
]==;
]==;
]==')maxn=4294967295ull;
]==')maxn=18446744073709551615ull;
}
ans=;now=;
all=1.0;
}){
now++;,len=strlen(str+);
)flag=-;
){;i<=;i++);}}
)||ans==-)ans=now;
//printf("%.2f\n",all);
){
va=;
;i<=len;i++)va=va*+str[i]-';
if(maxn<va)ans=now;maxn=maxn/va;
}
}
}
)printf("never\n");else printf("%d\n",ans);
;
fclose(stdin);fclose(stdout);
}
也不知道为何当场A了一片人啊。。。
T2：《函数变换》暴搜。。。。。被欧拉函数重新教育了一下。。。以后遇到这种问题要学会自己推。。。这道题的故事告诉我们：没事不要写记忆化QAQ吃力不讨好....最后一个点还是超。。。加了inline和读入优化还是超。。。卡常能力爆负。。。小鼹鼠的P比我快了整整1s。。。。。没事不要开long long。。。。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define N 2000000
using namespace std;
int cas,n,k;
int phi[N],flag[N],tot,prime[N];
inline int ph(int x){
)return phi[x];
,xx=x;
;i<=int(sqrt(xx));i++){
,l=;
){
s++;x/=i;l=l*i;
}
)l=l/i;
)t=t*l*(i-);
}
)t=t*(x-);
return t;
}
inline int dfs(int x,int rest){
||x==);
int s=ph(x);
;
)t=min(t,dfs(x/+,rest-)+);
return t;
}
inline int read(){
,f=;char ch=getchar();
'){
;ch=getchar();
}
'){
x=x*+ch-';ch=getchar();
}return x*f;
}
int main(){
freopen("func.in","r",stdin);freopen("func.out","w",stdout);
scanf("%d",&cas);
phi[]=;phi[]=;
;i<=;i++){
){
tot++;prime[tot]=i;phi[i]=i-;
}
;j<=tot;j++){
)break;
flag[i*prime[j]]=;phi[i*prime[j]]=phi[i]*(prime[j]-);
){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
}
}
//for(int i=1;i<=10;i++)printf("%d\n",phi[i]);
while(cas--){
//n=read();k=read();
scanf("%d%d",&n,&k);
printf("%d\n",dfs(n,k));
}
fclose(stdin);fclose(stdout);
}
func
T3：《跳跃切除子序列》总感觉这道题很暴力的样子。答案的结果不会很大，换句话说，可以直接枚举答案，接着枚举首项和公差，想明白了以后最大的压力还是实现这个东西。<最近写代码总是很焦躁>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int cas,a,len,ls,flag;ll xx;
],str[];
];
void dfs(int k,int al,int pi){
;return;}
)return;
//if(xx==93841336)printf("%d %d %d\n",k,al,pi);
if(s[k]==str[pi]){
if(pi==ls){int all=al;
;i<=len;i++){
all++;c[all]=i;
}
;
;i<=all;i++)]!=c[i-]-c[i-])ok=;
)dfs(len+,all,pi+);
},al,pi+);
}
al++;
c[al]=k;//if(xx==93841336)printf("%d %d %d\n",k,al,pi);
&&c[al]-c[al-]!=c[al-]-c[al-])return;
dfs(k+,al,pi);
}
int main()
{
freopen("jumpcut.in","r",stdin);freopen("jumpcut.out","w",stdout);
scanf("%d",&cas);
while(cas--){
scanf();ls=strlen(str+);
ll t=,x=;flag=;
){
t++;x=t*a;xx=x;;
){k++;s[k]=x%+;}//µ¹Ðò
;i<=k/;i++){
];s[k-i+]=ch;
}
len=k;
dfs(,,);
}
printf("%lld\n",xx);
}
fclose(stdin);fclose(stdout);
}
jumpcut
这道题教育我，永远不要太相信自己的肉眼查错能力，在很多情况下唯数据do help。不过这都是治标不治本的了>_<
第二场day2：
T1：mod。被中国剩余定理吓死了。超不爽，数据给了std都不给。。。数学这种东西。。。唉。。。
#include <cstdio>
#include <cstring>
#define f(x, y, z) for(int x = (y); x <= (z); ++x)
typedef long long LL;
inline bool prime(int x){
; i * i <= x; i++) ) return false;
return true;
}
], pn = , a[], n, b[], m;
struct num{
], mb[];
inline num(){
memset(mp, , sizeof(mp));
memset(mb, , sizeof(mb));
}
inline num(int x){
f(i, , n) mp[i] = x % p[i];
f(i, , m) mb[i] = x % b[i];
}
inline num &operator +=(const num &other){
f(i, , n) mp[i] = (mp[i] + other.mp[i]) % p[i];
f(i, , m) mb[i] = (mb[i] + other.mb[i]) % b[i];
}
inline num &operator *=(const num &other){
f(i, , n) mp[i] = mp[i] * other.mp[i] % p[i];
f(i, , m) mb[i] = (LL) mb[i] * other.mb[i] % b[i];
}
};
int main(){
scanf("%d%d", &n, &m);
p[] = ; a[] = ;
;; i++) if(prime(i)){
p[++pn] = i;
if(pn >= n) break;
}
f(i, , n) scanf("%d", a + i);
f(i, , m) scanf("%d", b + i);
num ans, prod = ;
bool zero = true;
f(i, , n){
while(ans.mp[i] != a[i]){
ans += prod;
zero = false;
}
prod *= p[i];
}
if(zero) ans = prod;
f(i, , m) printf("%d\n", ans.mb[i]);
;
}
神奇的std
T2：《净化》。这题没想到的确是我傻，搞一个超级源，算出所有居民点到水源距离，对于每一条水管都讨论一下，其实不是麻烦的事情。被数据骗了，30w写了10w。^(*￣(oo)￣)^写了个【dijk+堆】感觉越来越顺手了
#include<cstdio>
#include<algorithm>
#define N 300000
using namespace std;
,top;
,ans=;
int n,m,edgenum;
int q[N],vv[N],uu[N],ll[N],tt[N],flag[N],vet[N],next[N],head[N],pri[N];
long long dis[N];
void add(int u,int v,int w){
edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;
pri[edgenum]=w;
}
void push_down(){
;
<=top){
+<=top&&dis[q[k*+]]<dis[q[k]]&&dis[q[k*+]]<dis[q[k*]]){
swap(q[k],q[k*+]);k=k*+;
}]]<dis[q[k]]){
swap(q[k],q[k*]);k=k*;
}else break;
}
}
void push_up(int k){
>&&dis[q[k]]<dis[q[k/]]){
swap(q[k],q[k/]);
k=k/;
}
}
void ins(int k){
top++;q[top]=k;push_up(top);
}
void spfa(){
;i<=n;i++)dis[i]=inf;
dis[]=;ins();flag[]=;
while(top){
],e=head[u];q[]=q[top];
top--;push_down();
){
int v=vet[e];
if(dis[v]>dis[u]+pri[e]){
dis[v]=dis[u]+pri[e];
){
flag[v]==;ins(v);
}else push_up(v);
}
e=next[e];
}
}
}
int main()
{
freopen("purify.in","r",stdin);freopen("purify.out","w",stdout);
scanf("%d%d",&n,&m);
S=;
;i<=n;i++){
int x;
scanf()add(S,i,);
}
;i<=m;i++){
scanf("%d%d%d%d",&uu[i],&vv[i],&tt[i],&ll[i]);
add(uu[i],vv[i],ll[i]);
)add(vv[i],uu[i],ll[i]);
}
spfa();
//for(int i=1;i<=n;i++)printf("%d %lld\n",i,dis[i]);
;i<=m;i++){
int u=uu[i],v=vv[i],cost;
){
cost=dis[u]+ll[i];
}else{
if(dis[u]>dis[v])swap(u,v);
)/;
}
if(cost>ans)ans=cost;
}
printf("%lld",ans);
fclose(stdin);fclose(stdout);
}
dijk+heap
T3：《three》。据说yd现场200-切了，写起来太坑爹，我还是口胡一下把。由“观察”得知，只要把两两点对之间的距离求和/2，便是答案。先把环找出来，再把环破掉，各种分情况。。。。。。贴一个yd的代码！
#include <cstdio>
#include <algorithm>
using namespace std;
;
struct EG
{
int a, b, c;
} eg[N << ];
int head[N], en;
], dep[N], cir[N], belong[N], init[N], Q[N], rot[N], mir[N], b[N], c[N], sc[N], n, m, q, Dep[N];
void SetEdge(int u, int v, int w)
{
eg[++en] = (EG) {v, head[u], w};
head[u] = en;
init[v]++;
}
void dfs(int u, int r)
{
belong[u] = belong[fa[u][]];
rot[u] = r;
for (int e = head[u]; e; e = eg[e].b)
{
int v = eg[e].a;
]) continue;
if (cir[v]) continue;
fa[v][] = u;
dep[v] = dep[u] + eg[e].c;
Dep[v] = Dep[u] + ;
dfs(v, r);
}
}
int lca(int u, int v)
{
;
if (Dep[u] > Dep[v]) swap(u, v);
while (Dep[v] - Dep[u])
{
<< i))
v = fa[v][i];
i++;
}
if (u == v) return u;
; i >= ; i--)
if (fa[u][i] != fa[v][i])
u = fa[u][i], v = fa[v][i];
];
}
int query_tree(int u, int v)
{
int l = lca(u, v);
* dep[l];
}
int query_circle(int u, int v)
{
u = mir[u], v = mir[v];
if (u > v) swap(u, v);
]] - sc[v] + sc[u]);
}
int query_all(int u, int v)
{
if (belong[u] == belong[v])
return query_tree(u, v);
return query_circle(rot[u], rot[v]) + dep[u] + dep[v];
}
int main()
{
freopen("three.in", "r", stdin);
freopen("three.out", "w", stdout);
scanf("%d%d%d", &n, &m, &q);
if (m == n)
{
; i <= m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
SetEdge(u, v, w);
SetEdge(v, u, w);
}
, T = ;
; i <= n; i++)
) Q[++T] = i;
; i <= n; i++) cir[i] = ;
while (H <= T)
{
int u = Q[H++];
cir[u] = ;
for (int e = head[u]; e; e = eg[e].b)
{
int v = eg[e].a;
init[v]--;
) Q[++T] = v;
}
}
; i <= n; i++)
if (cir[i] && !belong[i])
{
belong[]++;
dfs(i, i);
}
; j <= ; j++)
; i <= n; i++)
fa[i][j] = fa[fa[i][j - ]][j - ];
{
int p;
; i <= n; i++) if (cir[i]) p = i;
int q, qq;
for (int e = head[p]; e; e = eg[e].b)
{
int v = eg[e].a;
if (cir[v]) q = v, qq = eg[e].c;
}
b[] = ;
b[] = p;
b[] = q;
c[] = qq;
mir[p] = ;
mir[q] = ;
)
{
, U;
]]]; e; e = eg[e].b)
{
int v = eg[e].a;
] - ]) continue;
if (cir[v]) u = v, U = eg[e].c;
}
])
{
c[] = U;
break;
}
b[++b[]] = u;
mir[u] = b[];
c[b[]] = U;
}
}
; i <= b[]; i++) sc[i] = sc[i - ] + c[i];
while (q--)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
if (belong[u] != belong[v] && belong[u] != belong[w] && belong[v] != belong[w])
{
int x = query_all(u, v), y = query_all(v, w), z = query_all(u, w);
printf("%d\n", min(x + y - dep[v], min(y + z - dep[w], x + z - dep[u])));
continue;
}
if (belong[u] == belong[w] && belong[u] != belong[v]) swap(v, w);
if (belong[v] == belong[w] && belong[u] != belong[v]) swap(u, w);
if (belong[u] == belong[v] && belong[u] != belong[w])
{
int l = lca(u, v);
printf("%d\n", query_tree(u, v) + query_all(l, w));
continue;
}
if (belong[u] == belong[v] && belong[u] == belong[w])
{
printf();
continue;
}
}
;
}
)
{
; i <= m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
SetEdge(u, v, w);
SetEdge(v, u, w);
}
dfs(, );
; j <= ; j++)
; i <= n; i++)
fa[i][j] = fa[fa[i][j - ]][j - ];
while (q--)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
printf();
}
;
}
}
YD的代码
厦门day1：
T1：《数列》。发现f(x,y)==f(y,x)，且能走到的位置一定是gcd（x，y）的倍数。。。做的过程中我走了很多弯路。。希望下次能推得顺利一点
T2：《treasure》。感觉std的状态略麻烦，我只记录了走回root的最大值，停在下面的最大值和次大值（相信大部分人都是这样的）。
T3：《三角形》。咦。。这道题的奇技淫巧真是闻所未闻。。见所未见。。。（手动滑稽）出题人的做工估计全在N和Q上，O（q/k*n^2+q*k+q*n）,当且仅当k=1000时能通过时限。（事实证明std在本地跑不仅超时而且超内存，口亨）.....个人觉得难点在于怎样打tag重构差分数组以及O（1）算某操作对于某询问的贡献。最慢的点跑了1.2s，不过std也彼此彼此啦。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 1001010
using namespace std;
int t,n,q,x[N],y[N],l[N];
ll tag[][],sum[][];
void rebuild()
{
memset(tag,,sizeof(tag));
;t--){
int x0=x[t],y0=y[t],l0=l[t];
for(int j=y0,i=x0;j<y0+l0;i++,j++){
tag[j][i]++;tag[j][x0+l0]--;
}
}
;j<=n;j++){
ll now1=,now2=;
for(int i=j;i<=n;i++){
now1+=tag[j][i];now2+=now1;
sum[j][i]+=now2;
}
}
}
int main()
{
freopen("delta.in","r",stdin);freopen("delta.out","w",stdout);
scanf(;
while(q--){
int op;
scanf("%d",&op);
){
t++;scanf("%d%d%d",&x[t],&y[t],&l[t]);
)rebuild();
}else{
int x0,y0,l0;scanf("%d%d%d",&x0,&y0,&l0);
ll ans=;
;j<y0+l0;i++,j++)
ans+=sum[j][x0+l0-]-sum[j][i];
//printf("===%lld\n",ans);
;i<=t;i++){//O(1)
||x[i]>x0+l0-)continue;
||y[i]>y0+l0-)continue;
ll mx=min(x0+l0-,x[i]+l[i]-);
ll xx=max(y0,y[i]),yy=min(y0+mx-x0,y[i]+mx-x[i]);
ll len=yy-xx+;//printf("===%lld\n",len);
)continue;
ans+=len*(len+)/;
}
printf("%lld\n",ans);
}
}
}
delta
厦门day2：
T1：《sort》。想来没什么好说的。
T2：《graph》。暴力打错不开心。原因是作死多打一句判断而且还打错。正解：看到竞赛图的敏感性*！。。。纸上得来终觉浅，但仍需动笔画一画。。。
#include<cstdio>
#include<algorithm>
#define N 3000
using namespace std;
char str[N];
][],b[][];
void tarjan1(int u){
)return;
tm++;dfn[u]=tm;low[u]=tm;top++;stack[top]=u;
;v<=n;v++)){
){
tarjan1(v);low[u]=min(low[u],low[v]);
})low[u]=min(low[u],low[v]);
}
if(low[u]==dfn[u]){
id++;size[id]=;yt[u]=id;
while(stack[top]!=u){
size[id]++;yt[stack[top]]=id;top--;
}top--;)flag=;//printf("%d %d\n",u,size[id]);
}
}
void tarjan2(int u){
)return;
tm++;dfn[u]=tm;low[u]=tm;top++;stack[top]=u;
;v<=n;v++)||b[u][v]==)){
){
tarjan2(v);low[u]=min(low[u],low[v]);
})low[u]=min(low[u],low[v]);
}
if(low[u]==dfn[u]){
id++;size[id]=;yt[u]=id;
while(stack[top]!=u){
size[id]++;yt[stack[top]]=id;top--;
}top--;)flag=;
}
}
int main()
{
freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);
scanf("%d",&cas);
while(cas--){
scanf(;
;i<=n;i++);j<=n;j++)a[i][j]=,b[i][j]=;
;i<=n;i++){
scanf();
;j<=n;j++)
;else
;
}
flag=;;i<=n;i++)dfn[i]=,size[i]=,yt[i]=;top=,id=,tm=;
;i<=n;i++))tarjan1(i);
){printf("N\n");continue;}
;i<=n;i++)dfn[i]=,size[i]=,yt[i]=;top=,id=,tm=;
flag=;;i<=n;i++))tarjan2(i);
){printf("N\n");continue;}
flag=;;i<=n;i++)dfn[i]=,yt[i]=,size[i]=;top=,id=,tm=;
;i<=n;i++);j<=n;j++)){a[j][i]=;}
//for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d",a[i][j]);printf("\n");}
;i<=n;i++))tarjan1(i);
){printf("N\n");continue;}
printf("T\n");
}
fclose(stdin);fclose(stdout);
}
graph
T3：《or》。暴力打错不开心。另外题目中没给出取模坑害不少人，虽然坑的不是我。正解：数位DP。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000100
#define ll long long
#define mo 1000000007
using namespace std;
;ll ans,c[N],len;
];
ll f[N][][],g[N][][];
int calc(int x,int y,int z){
);
&&z==x);
&&z<x);
&&z>x);
}
int main()
{
freopen("or.in","r",stdin);freopen("or.out","w",stdout);
scanf("%d",&n);
scanf();
;i<=n;i++)c[i]=str[i]-';
f[][][]=;g[][][]=;
;i<=n;i++)
;j<=;j++)
;k<=;k++)//i-1
;a<=;a++)//r
;b<=;b++){//l
int u=calc(c[i],j,a),v=calc(a,k,b);
&&v!=-){
if(a|b){
f[i][u][v]=(f[i][u][v]+(f[i-][j][k]+g[i-][j][k])%mo)%mo;
g[i][u][v]=(g[i][u][v]+g[i-][j][k])%mo;
}else{
f[i][u][v]=(f[i][u][v]+f[i-][j][k])%mo;
g[i][u][v]=(g[i][u][v]+g[i-][j][k])%mo;
}
}
}
;j<=;j++)
;k<=;k++)ans=(ans+f[n][j][k])%mo;
printf("%lld",ans);
fclose(stdin);fclose(stdout);
}
or
湖南day1：
T1：《geometry》。想来没什么好说的。
T2：《party》。一开始真的不会做。都是乌龟教的好——%%%北大龟。
T3：《editor》。暴力拿了90分。>_<正解双向链表。打得弃坑了。。。。so verbose。。。。难过。。。。tag写不清楚。。。。什么都不想说了。。。update14：04：下午脑子清楚了很多。。。。。去掉tag后就A了，因为用了偷懒的写法，所以常数有点爆炸。。。最后一个点要跑5s。。。不管了。。。丢代码跑
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;
#define N 10000000
int pre[N], suf[N];
char ch[N], st[N];
], cnt[];
inline void swap(int &a, int &b) {
int c = a;
a = b;
b = c;
}
void Insert(int opt, char c) {
++idx;
ch[idx] = c;
int u = pos[opt], v = suf[u];
pre[idx] = u; suf[idx] = v;
suf[u] = idx; pre[v] = idx;
] >= cnt[opt]) cnt[opt^]++;
pos[opt] = idx; cnt[opt]++;
] == u) pos[opt^] = idx;
puts("T");
}
void LMove(int opt) {
) {
puts("F");
return ;
}
int u = pos[opt], v = pre[u];
if (suf[v] != u) swap(suf[v], pre[v]);
pos[opt] = v; cnt[opt]--;
puts("T");
}
void RMove(int opt) {
) {
puts("F");
return ;
}
int u = suf[pos[opt]], v = suf[u];
if (pre[v] != u) swap(suf[v], pre[v]);
pos[opt] = u; cnt[opt]++;
puts("T");
}
void Delete(int opt) {
) {
puts("F");
return ;
}
int u = pos[opt], v = suf[u], w = suf[v];
if (pre[w] != v) swap(suf[w], pre[w]);
] > cnt[opt]) cnt[opt^]--;
] == v) pos[opt^] = u;
suf[u] = w; pre[w] = u;
puts("T");
}
void Reverse() {
] - cnt[] <= ) {
puts("F");
return ;
}
] - cnt[] == ) {
puts("T");
return ;
}
], b = suf[a], c = pos[], d = suf[c];
swap(pre[b], suf[b]); swap(pre[c], suf[c]);
suf[a] = c; pre[c] = a; suf[b] = d; pre[d] = b;
pos[] = b;
puts("T");
}
void Show() {
;
while (true) {
if (pre[suf[u]] != u) swap(pre[suf[u]], suf[suf[u]]);
u = suf[u];
) break;
putchar(ch[u]);
}
putchar('\n');
}
void Build() {
gets(st);
idx = ;
pre[] = -; suf[] = ;
pre[] = ; suf[] = -;
pos[] = pos[] = cnt[] = cnt[] = ;
int len = strlen(st);
; i < len; i++) {
++idx;
ch[idx] = st[i];
pre[idx] = i == ? : idx - ;
suf[idx] = i == len - ? : idx + ;
}
) {
suf[] = ; pre[] = idx;
pos[] = idx; cnt[] = len + ;
}
}
inline int Dir() {
getchar();
: ;
}
int main() {
freopen("editor10.in", "r", stdin);
freopen("editor10.out", "w", stdout);
Build();
int m;
scanf("%d",&m);
; i <= m; i++) {
getchar();
char opt = getchar();
if (opt == '<') LMove(Dir());
else if (opt == '>') RMove(Dir());
else if (opt == 'I') {
int d = Dir();
char c = ' ';
|| c > ) c = getchar();
Insert(d, c);
}
else if (opt == 'D') Delete(Dir());
else if (opt == 'R') Reverse();
else if (opt == 'S') Show();
}
;
}
std
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10000100
using namespace std;
char str[N];
,tail=;
void add(int x,int y){
pro[x]=y;pre[y]=x;
}
void fan(int ff,int x){
if(x==head||x==tail)return;
){
int k=pre[x];
if(k==head||k==tail)return;
if(pro[k]!=x)swap(pre[k],pro[k]);
}else{
int k=pro[x];
if(k==head||k==tail)return;
if(pre[k]!=x)swap(pre[k],pro[k]);
}
}
int main()
{
freopen("editor.in","r",stdin);freopen("editor.out","w",stdout);
scanf();
scanf();
l=;r=n;ll=;rr=n;
pro[]=;pro[n]=tail;
;i<n;i++)pro[i]=i+,pre[i+]=i;
pre[]=head;
pre[tail]=n;
while(cas--){
];
scanf();fan(,pro[l]);fan(,pro[l]);fan(,r);fan(,r);
]=='<'){
c=getchar();c=getchar();
if(c=='L'){
if(l==head)printf("F\n");else printf("T\n"),l=pre[l],ll--;
}else{
if(r==head)printf("F\n");else{printf("T\n");r=pre[r];rr--; }
}
}]=='>'){
c=getchar();c=getchar();
if(c=='L'){
if(pro[l]==tail)printf("F\n");else {printf("T\n");l=pro[l];ll++;}
}else{
if(pro[r]==tail)printf("F\n");else printf("T\n"),r=pro[r],rr++;
}
}]=='I'){
c=getchar();c=getchar();
if(c=='L'){
c=getchar();c=getchar();int k=pro[l];
tot++;str[tot]=c;add(l,tot);add(tot,k);l=tot;ll++;if(rr>=ll)rr++;
}else{
c=getchar();c=getchar();int k=pro[r];
tot++;str[tot]=c;add(r,tot);add(tot,k);r=tot;rr++;if(ll>=rr)ll++;
}
printf("T\n");
}]=='D'){
c=getchar();c=getchar();
if(c=='L'){
if(pro[l]==tail)printf("F\n");else{
printf("T\n");
int k=pro[pro[l]];add(l,k);if(rr>ll)rr--;
}
}else{
if(pro[r]==tail)printf("F\n");else{
printf("T\n");
int k=pro[pro[r]];add(r,k);if(ll>rr)ll--;
}
}
}]=='R'){
if(ll<rr){
printf("T\n");
int x=pro[l],y=r,a=l,d=pro[r];
swap(pre[x],pro[x]);swap(pre[y],pro[y]);
add(a,y),add(x,d);r=x;
}else printf("F\n");
}]=='S'){
,i);}
printf("\n");
}
}
fclose(stdin);fclose(stdout);
}
My Code
湖南day2：
T1：《sort》。默默写挂。订正得十分艰难，贪心要好好想。。输入输出优化要好好写。。。
#include<cstdio>
#include<algorithm>
#define N 1000100
using namespace std;
];
int read(){
,f=;
'){
;
ch=getchar();
}
'){
x=x*+ch-';ch=getchar();
}return x*f;
}
void print(int m){
;
){
h++;g[h]=ans[m]%;ans[m]/=;
}
;i--)putchar(g[i]+');if(m<n)putchar(' ');
}
int main()
{
freopen("sort.in","r",stdin);freopen("sort.out","w",stdout);
scanf("%d",&n);
;i<=n;i++){
a[i]=read();
}
,j=,now=n,tot=;
;i--){
&&q[top]>i)tot=tot+,ans[tot]=q[top],,top=top-;
){
j++;top++;q[top]=a[j];;
}
if(q[top]==i){
tot++;ans[tot]=i;top--;;chu[i]=;
}
}
)tot=tot+,ans[tot]=q[top],top=top-;
;i<=n;i++)print(i);
;
fclose(stdin);fclose(stdout);
}
sort
T2：《forest》。暴力拿了80分。每天T2都不会。。不开心。因为出题人写了ai小于等于多少却没写大于等于0，导致我以为可以出现负数，那么问题就变得复杂了QAQ。。。注意换树根的时候四个端点分别都考虑一下。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mo 1000000007
#define ll long long
#define N 200010
using namespace std;
],next[N],de[N],uu[N],ff[N],vv[N],head[N],vet[N],value[N],zuo[N],you[N];
ll ans=,inf=,tree[N],dist[N],aa[N],now;
inline void add(int u,int v){
edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;
}
inline int find(int x){
if(ff[x]!=x)ff[x]=find(ff[x]);return ff[x];
}
inline ll max(ll a,ll b){if(a>b)return a;else return b;}
inline ll quickmi(ll a){
;ll tmp=;
){
==)tmp=tmp*a%mo;
a=a*a%mo;k=k/;
}return tmp;
}
inline void dfs(int u,int ff,ll xx,int deep){
dep[u]=deep;dist[u]=xx;
int e=head[u];
){
int v=vet[e];
if(v!=ff){
fa[v][]=u;dfs(v,u,xx+value[v],deep+);
}
e=next[e];
}
}
ll query(int x,int y){
int xx=x,yy=y;
if(dep[x]<dep[y])swap(x,y);
;i>=;i--)<<i))>=dep[y])x=fa[x][i];
;i>=;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
],y=fa[y][];
//printf("%d %d %d\n",xx,yy,x);
+value[x];
}
int main()
{
freopen("forest.in","r",stdin);freopen("forest.out","w",stdout);
scanf("%d",&n);
;i<=n;i++)scanf("%d",&value[i]),ans=ans*value[i]%mo,tree[i]=value[i],ff[i]=i,zuo[i]=i,you[i]=i;
;i<=n-;i++){
int u,v;scanf("%d%d",&u,&v);uu[i]=u;vv[i]=v;add(u,v);add(v,u);
}
dfs(,,value[],);
;i<=;i++);j<=n;j++)fa[j][i]=fa[fa[j][i-]][i-];
aa[n]=ans;
edgenum=;memset(head,,sizeof(head));
;i<=n-;i++)scanf("%d",&de[i]);
;q>=;q--){
int u=uu[de[q]],v=vv[de[q]],x=find(u),y=find(v);
ll tmp=;
ans=ans*quickmi(tree[x])%mo;ans=ans*quickmi(tree[y])%mo;
int l1=zuo[x],r1=you[x],l2=zuo[y],r2=you[y];
if(query(l1,r1)>tmp){
tmp=query(l1,r1);zuo[x]=l1,you[x]=r1;
}
if(query(l1,r2)>tmp){
tmp=query(l1,r2);zuo[x]=l1;you[x]=r2;
}
if(query(l1,l2)>tmp){
tmp=query(l1,l2);zuo[x]=l1;you[x]=l2;
}
if(query(l2,r1)>tmp){
tmp=query(l2,r1);zuo[x]=l2;you[x]=r1;
}
if(query(l2,r2)>tmp){
tmp=query(l2,r2);zuo[x]=l2;you[x]=r2;
}
if(query(r1,r2)>tmp){
tmp=query(r1,r2);zuo[x]=r1;you[x]=r2;
}
ff[y]=x;tree[x]=tmp;ans=ans*tmp%mo;
aa[q]=ans;
}
;i<=n;i++)printf("%lld\n",aa[i]);
;
fclose(stdin);fclose(stdout);
}
forest
T3：《sp》。环套树可以拿80分。没想到正解真的是仙人掌（防AK？），这题是bzoj2125. 但是总有出题人想谋害朕，说好的80分，第一个点就来了两个环>_<猝死了，看了CC的代码，get了一种找环新技巧bcj，然后炸出了双联通分量（代码见暑假tarjan专题）。。。。。仙人掌确实很优美，but，联赛前夕还是干点“更有用的事”吧（懒），以后有时间一定把它切了~
lyy场day1：
T1：《挑战nbc》。想来没什么好说的。
T2：《论战大原题》。超不爽，历年联赛题没有订正。超不爽，程序刚打完系统重启了。不知道是不是刚重置了浏览器的原因。。。也懒得再写一遍了。寻找最长路上的最小边。要求kruskal求一棵最大生成树，然后dfs需要N^2，std精妙地O（n）处理了，因为每次贪心加边，所以当前加上的边一定是两个联通块中最小的，直接算ans即可。
#include <cstdio>
#include <algorithm>
], w[], N, M;
struct edge
{
int u, v, w;
}
p[];
long long K;
inline bool operator < (const edge &a, const edge &b)
{
return a.w > b.w;
}
int F(int x)
{
return f[x] == x ? x : (F(f[x]), f[x] = f[f[x]]);
}
int main()
{
freopen("original.in", "r", stdin);
freopen("original.out", "w", stdout);
scanf("%d%d%lld", &N, &M, &K);
; i < M; i++)
scanf("%d%d%d", &p[i].u, &p[i].v, &p[i].w);
std::sort(p, p + M);
; i <= N; i++)
f[i] = i, w[i] = ;
; i < M; i++)
{
int u = F(p[i].u), v = F(p[i].v);
if (u != v)
{
K -= (long long)w[u] * w[v];
f[u] = v, w[v] += w[u];
}
)
;
}
;
}
贴lyy的std
T3：《鏖战字符串》。%%%lyy。关于前50分一个暴力dp即可，不得不说这50分lyy放得还是蛮良心的。然而这是一道**题。第一个单调队列，是一个分段平方和，写得仔细点就行了。第三个单调队列可以用线段树代替（就是感觉这样写耗脑量较少罢了）。第二个其实最困难：先发现对于每一个i，能转移到它的点一定是一个区间（j~i中最多字符在[L,R]），左端点保证区间内最大值小于等于R，右端点保证大于等于L，不明白为什么可以直接倍增w，加入i字符，如果它的值大于R了，则左端点前移，那么右端点什么时候前移呢？如果i字符是最大字符且加上后刚好够L，那就前移一直移动到相同字符处，这样每次都保证了当前字符有L个。这道题写得很爽，因为1A了。(●'◡'●)
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 200020
#define ll long long
using namespace std;
int n,L,R;char str[N];
int dif[N],q[N],cntl[N],cntr[N];
ll sum[N],dp[N],A,B,C,D,tree[];
ll min(ll a,ll b){if(a<b)return a;else return b;}
ll sqr(ll x){return x*x;}
int pd(int k,int j,int i){
ll fenzi=dp[j]-dp[k]+A*(sqr(sum[j])-sqr(sum[k]));
ll fenmu=A*(sum[j]-sum[k])*;;;
}
int calc(int k,int j,int i){
ll fenzi1=dp[j]-dp[k]+(sqr(sum[j])-sqr(sum[k]))*A,fenmu1=sum[j]-sum[k];
ll fenzi2=dp[i]-dp[j]+(sqr(sum[i])-sqr(sum[j]))*A,fenmu2=sum[i]-sum[j];
return fenzi1*fenmu2>=fenzi2*fenmu1;
}
void update(int x,int st,int ed,int p,ll v){
if(x==st&&x==ed){tree[p]=v;return;}
;
,ed,p+p+,v);
tree[p]=min(tree[p+p],tree[p+p+]);
}
ll query(int l,int r,int st,int ed,int p){
//printf("%d %d %d %d\n",l,r,st,ed);
;
,ed,p+p+);
,r,mid+,ed,p+p+));
}
int main()
{
freopen("string.in","r",stdin);freopen("string.out","w",stdout);
scanf("%d%lld%lld%lld%lld%d%d",&n,&A,&B,&C,&D,&L,&R);
scanf();str[]=;
;i<=n;i++)scanf(]+dif[i];
,r=,nowl=,nowr=;
;i<=n;i++){
],i)==)l++;
int k=q[l];dp[i]=dp[k]+sqr((sum[i]-sum[k]))*A+B;
;
cntl[xx]++;cntr[xx]++;
while(cntl[xx]>R){
cntl[str[nowl]-]--;nowl++;
}
while(cntr[xx]>=L){
if(str[nowr]==str[i]&&cntr[xx]==L)break;
cntr[str[nowr]-]--;
nowr++;
}
if(nowl<=nowr){
ll tmp=query(nowl-,nowr-,,n,);//printf("%lld\n",tmp);
tmp=tmp+C*sum[i]+D;if(tmp<dp[i])dp[i]=tmp;
}
update(i,,n,,dp[i]-C*sum[i]);
],q[r],i))r--;r++;q[r]=i;
}
;i<=n;i++)printf("%lld\n",dp[i]);
;
fclose(stdin);fclose(stdout);
}
string
lyy场day2：
T1：《怎样更有力气》。想说这是一道好题。不光是因为它萌萌哒题面。lyy总能通过其惊人的实力与智慧来提醒我们一些道理。比如：记得想二分！！！写起来细节很多，要防止TLE。
#include<cstdio>
#include<algorithm>
#define N 200020
#define ll long long
using namespace std;
ll n,len;int m;
struct node{ll l,r,h;}a[N],b[N];
bool cmp(node a,node b){if(a.l==b.l)return a.r<b.r; return a.l<b.l;}
int pd(int tag){
;i<=tag;i++)
b[i].l=a[i].l,b[i].r=a[i].r;
sort(b+,b+tag+,cmp);
ll L=,rest=;
;i<=tag;i++){
){L=max(b[i].r,L);continue;}
);ll tmp=((b[i].l--L-)/len)+;
rest+=tmp;L=L+tmp*len;
L=max(b[i].r,L);//printf("<>===%d\n",L);
}
while(L<n){
L+=len;rest++;;
}
;;
}
int main()
{
freopen("liqi.in","r",stdin);freopen("liqi.out","w",stdout);
scanf("%lld%d%lld",&n,&m,&len);
;i<=m;i++)
scanf("%lld%lld",&a[i].l,&a[i].r),a[i].h=i;
,r=m;
while(l<r){
;
;
}
)printf("Poor Douer!");else printf("%d",r);
fclose(stdin);fclose(stdout);
}
liqi
T2：《怎样学习哲学》。长得很像APIO2016赛艇。极好的DP。好写不好想，从p个空点上下功夫就可以C一下了，最后再加一个【n+1,m+1】，一开始我还担心要容斥什么的，后来发现精妙的定义保证了每个点的dp都是在前i个点中只有i空点的答案。要用线性求逆元，其实个人感觉就算不会了，每次P^2搞一个快速幂也是可以的？（大雾）
#include<cstdio>
#include<algorithm>
#define mo 1000003
#define N 1001000
#define ll long long
using namespace std;
struct node{int x,y;}a[N];
ll jie[N],inv[N],dp[N];
int n,m,p;
bool cmp(node a,node b){return a.x<b.x;}
ll c(int n,int m){
;
if(n<mo)return jie[n]*inv[m]%mo*inv[n-m]%mo;
else return c(n/mo,m/mo)*c(n%mo,m%mo)%mo;
}
int main()
{
freopen("zhexue.in","r",stdin);freopen("zhexue.out","w",stdout);
scanf("%d%d%d",&n,&m,&p);
;i<=p;i++){
scanf("%d%d",&a[i].x,&a[i].y);
} sort(a+,a+p+,cmp);
jie[]=;;i<mo;i++)jie[i]=(jie[i-]*i)%mo;
inv[]=;;i<mo;i++)inv[i]=inv[mo%i]*(mo-mo/i)%mo;
inv[]=;;i<mo;i++)inv[i]=(inv[i-]*inv[i])%mo;
p++;a[p].x=n+;a[p].y=m+;
;i<=p;i++){
dp[i]=c(a[i].y-,a[i].x-);
;j<i;j++){
ll tmp=dp[j]*c(a[i].y-a[j].y-,a[i].x-a[j].x-)%mo;
dp[i]=(dp[i]-tmp+mo)%mo;
}
}
printf("%lld",dp[p]);
;
fclose(stdin);fclose(stdout);
}
zhexue
T3：《怎样打好隔膜》。感觉lyy是一个好的出题人。可惜我这种辣鸡选手也许无法在比赛中get到良心部分分的诚意了。亏我还在八中上面做过数据备份了，完全没有联系到那边去~~应该先看到这个很像欧拉回路问题，一个图存在欧拉路当且仅当存在两个奇点（度数为奇数的点）或不存在奇点。那么问题转化为：给定n个a[i]，选出k个a[i]满足两两不相邻且和最小。这样就可以使用链表和堆了。只需要将所有的奇点对消除，离散一下，记得堆要反向标记。任性，不写了。（最后的吐槽：看题解的时候耳机里正好放到《烟花易冷》，配上这道题的题面就是“遁空门”“前世过门”~，各种幽各种诡，┏┛┗┓...(((m -__-)m
安徽师大附中：
T1：《lca》。推了个O(n)就不想推了。。。想想50分也差不多了就这么点实力。。。结果考试快结束的时候GG日常黑了一把，发现我T1没写标算，后来又在shy那里get到了方法与公式，就粗略学习了一下然后。。。嘿嘿嘿
T2：《lcps》。写了50分的暴力dp也不想写了。后来想想T3也拿不到什么分数就开始写了一个“伪正解”，就是感觉自己可过但是怎么看都不觉得像标算。最后简单粗暴地写挂4个点，判最后一个字符的时候失手了。所以说，再自信的代码，还是无法正视淋漓的wa。
T3：《rw》。都不知道有多少人写了这道期望，毕竟都炸出“朝天走”这种算法了。坐等题解。update11/13：果然是需要朝天走。关于i->fa[i]这条有向边，i的子树中每一条边竟然都是等概率的，所以 f[<i,fa[i]>]=2*siz[i]-1，同理 f[<fa[i],i>]=2*(n-siz[i])-1，所以 f[<i,fa[i]>]+f[<fa[i],i>]=2(n-1)。继续考虑dp,关于每一个i作为lca，往它的j子树里找个最大的b[j]+f[j][i],再往它其它子树k里找个最大的a[k]+f[i][k]，这个可以用前缀max和后缀max。