BruceJay's Blog

Bruce之NOIP模拟考梦靥系列三

| Comments

扯淡

第一次NOIP全真模拟(全真个毛)。
同J房的大牛都用上了各种高级的与众不同的算法,Bruce只会朴素的算法,水平差距显而易见。

Day1

Solution

[Description]

对于方程,给定n,m,最多只有一个xi大于m,求解集的个数。

[Hint]

[Solution]

别看Hint(坑人的),过了7 150,8 80,18 18就行了。
这题貌似只有搜索,但裸搜显然过不了,可以进行这几个优化:
1.很显然,x1,x2...,xn可以默认为一个不降的序列。
2.如果后面怎么加(xi到xn都是xi-1)都会小于1,那么直接剪枝。
3.同理,如果后面怎么加(xi到xn-1全部都是m)都会大于1,那么直接剪枝。
这样就可以AC了。
注意double会坑,所以用分子分母存,要爆longlong时求个gcd。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const ll lim = 1e15;
int n,m,ans=0;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

void Dfs(int x,int now,ll a,ll b)
{
    if(b*(n-x)>=(b-a)*m) return;
    if(b*(n-x+1)<(b-a)*now) return;
    if(x==n){
        if(b%(b-a)==0) ans++;
        return;
    }
    if(b>lim){
        ll g=gcd(a,b);
        a/=g; b/=g;
    }
    for(int i=now;i<=m;i++) Dfs(x+1,i,a*i+b,b*i);
}

int main()
{
    freopen("solution.in","r",stdin);
    freopen("solution.out","w",stdout);
    scanf("%d%d",&n,&m);
    Dfs(1,1,0,1); printf("%d",ans);
    return 0;
}

Snake

[Description]

给定一张有向图,判断是否存在环。

[Hint]

[Solution]

同J房某些同学用了Tarjan求Scc,Bruce只会低端的拓扑排序。

[Code]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 20100;
const int M = 100100;
struct Edge{int v,nxt;}a[M];
int head[N]; int d[N]; int q[N];
int T,n,m;

inline int read()
{
    int x=0,t=1; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

bool Topo()
{
    int l=1,r=0;
    for(int i=1;i<=n;i++) if(!d[i]) q[++r]=i;
    while(l<=r){
        int u=q[l++];
        for(int i=head[u];i;i=a[i].nxt){
            int v=a[i].v;
            if(--d[v]==0) q[++r]=v;
        }
    }
    return r==n;
}

int main()
{
    int u,v;
    freopen("snake.in","r",stdin);
    freopen("snake.out","w",stdout);
    T=read();
    while(T--){
        n=read(); m=read();
        memset(head,0,sizeof(head));
        memset(d,0,sizeof(d));
        for(int i=1;i<=m;i++){
            u=read(); v=read();
            a[i].v=v; d[v]++;
            a[i].nxt=head[u]; head[u]=i;
        }
        if(Topo()) puts("Yes");
        else puts("No");
    }
    return 0;
}

Fight

[Description]

雷锋.W大战J形Codeplay0314,雷锋.W有A滴血,Codeplay0314有B滴血,雷锋.W每回合有三种选择:
Attack:甩掉耳朵,全力攻击Codeplay0314,对其造成X点伤害。
Defend:在海中央看不到岸的地方翻转摩托艇,让Codeplay0314看不见他,无法进行攻击。
Heal:怒吃电池,回血Y点。
每回合雷锋.W行动完后,然后Codeplay0314行动了,他发出鬼畜叫声,第i回合对雷锋.W造成ci点伤害。
血小于等于0就挂了.....
求雷锋.W是否能击败Codeplay0314,如果能,求最短几回合战胜;如果不能,求最多能掉Codeplay0314多少血。

[Hint]

[Solution]

贪心。
尽可能去攻击,如果要死了,就去防止之前受到的最大的伤害(可以将此伤害防御,也可以选择回血)。
没看懂看代码咯。

[Code]

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100100;
int c[N];
priority_queue<int> h;
int n,X,Y,A,B,Attack=0,MaxAttack=0;

inline int read()
{
    int x=0,t=1; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

int main()
{
    freopen("fight.in","r",stdin);
    freopen("fight.out","w",stdout);
    n=read(); X=read(); Y=read();
    A=read(); B=read();
    for(int i=1;i<=n;i++) c[i]=read();
    for(int i=1;i<=n;i++){
        h.push(c[i]); Attack++;
        B-=X; A-=c[i];
        MaxAttack=max(MaxAttack,Attack);
        if(B<=0) {printf("Win\n%d",i);return 0;}
        if(A<=0){
            A+=max(h.top(),Y); h.pop();
            Attack--; B+=X;
        }
    }
    printf("Lose\n%d",X*MaxAttack);
    return 0;
}

Day2

holiday

[Description]

给定一棵n个节点的带权树,对于任意点对(u,v),如果(u,v)不是树边,则(u,v)的花费为u到v的路径上权最大的树边的权值+1,求这棵树的权值总和。

[Hint]

[Solution]

同J房大神St_Saint用到了高端的切断树边的方法,而Bruce只会低端的并查集。
将边按权值升序排序,进行并查集。对于边(u,v,w),找到当前u和v所在连通块,对于u所在连通块上任意一点x和v所在连通块上任意一点y,cost(x,y)=w+1,所以这条边对答案的贡献为

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 100100;
struct Edge{int u,v,w;}a[N];
bool cmp(const Edge& a1,const Edge& a2)
{return a1.w<a2.w;}
int p[N]; int sz[N];
int T,n; ll ans;

inline int read()
{
    int x=0,t=1; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

int Find(int x){return p[x]==x?p[x]:p[x]=Find(p[x]);}

int main()
{
    freopen("holiday.in","r",stdin);
    freopen("holiday.out","w",stdout);
    T=read();
    while(T--){
        n=read(); ans=0;
        for(int i=1;i<n;i++){
            a[i].u=read(); a[i].v=read(); a[i].w=read();
        }
        sort(a+1,a+n,cmp);
        for(int i=1;i<=n;i++) p[i]=i,sz[i]=1;
        for(int i=1;i<n;i++){
            int u=Find(a[i].u),v=Find(a[i].v);
            ans+=(ll)(a[i].w+1)*((ll)sz[u]*sz[v]-1);
            p[u]=v; sz[v]+=sz[u];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

lis

[Description]

给定一个长度为n的序列,求任意删掉连续L个数后最长不降子序列的长度。

[Hint]

[Solution]

同J房同学都用了树状数组线段树之类的,Bruce不会,只用了低端的二分。
设g[i]以i为尾的lis最长长度,f[i]以i为头的lis最长长度,答案显然就是max(g[j]+f[i])(a[j]<=a[i],i>j+L)。
先二分求出f[i],再在[1,i-L-1]上二分求出j,更新答案。

[Code]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100100;
int tmp[N]; int a[N]; int f[N];
int n,L,ans=0,len=0;

inline int read()
{
    int x=0,t=1; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

int Find(int x)
{
    int l=1,r=len,res=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(tmp[mid]<=x) l=mid+1,res=mid;
        else r=mid-1;
    }
    return res;
}

int main()
{
    freopen("lis.in","r",stdin);
    freopen("lis.out","w",stdout);
    n=read(); L=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=n;i;i--){
        int pos=Find(-a[i]);
        tmp[pos+1]=-a[i];
        if(pos==len) len++;
        f[i]=pos+1;
    }
    memset(tmp,0,sizeof(tmp));
    len=0;
    for(int i=L+1;i<=n;i++){
        int pos=Find(a[i]);
        ans=max(ans,pos+f[i]);
        pos=Find(a[i-L]);
        tmp[pos+1]=a[i-L];
        if(pos==len) len++;
    }
    ans=max(ans,len);
    printf("%d",ans);
    return 0;
}

Milk

[Description]

求二维字符串的最小循环节。

[Hint]

[Solution]

分别以行和列为待匹配元素做KMP找出循环节。两个相乘就是答案。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10100;
const int M = 80;
char s[N][M]; int fail[N];
int n,m;

int gcd(int x,int y){return y?gcd(y,x%y):x;}

bool Match1(int x,int y)
{
    for(int i=1;i<=m;i++)
        if(s[x][i]!=s[y][i]) return false;
    return true;
}

bool Match2(int x,int y)
{
    for(int i=1;i<=n;i++)
        if(s[i][x]!=s[i][y]) return false;
    return true;
}

int Solve()
{
    int ans,now=0;
    for(int i=2;i<=n;i++){
        while(now && !Match1(now+1,i)) now=fail[now];
        if(Match1(now+1,i)) now++;
        fail[i]=now;
    }
    ans=n-fail[n]; now=0;
    for(int i=2;i<=m;i++){
        while(now && !Match2(now+1,i)) now=fail[now];
        if(Match2(now+1,i)) now++;
        fail[i]=now;
    }
    return ans*(m-fail[m]);
}

int main()
{
    freopen("milk.in","r",stdin);
    freopen("milk.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("\n%s",s[i]+1);
    printf("%d",Solve());
    return 0;
}

Comments

comments powered by Disqus