AGC002

A – Range Product

题意:

给你两个边界,问a\to b的所有值相乘是正数负数还是零.

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define P pair<int,int>
const LL inf = 0x3f3f3f3f;
const LL mod = 1e9+7;
const LL N = 4e3+10;
template <typename tp> inline void read(tp &x)
{
    x=0;char c=getchar();int f=0;
    for(;c>'9'||c<'0';f|=(c=='-'),c=getchar());
    for(;c<='9'&&c>='0';x=(x<<3)+(x<<1)+c-'0',c=getchar());
    if(f) x=-x;
}
int a,b;
int main()
{
    read(a),read(b);
    if(a<=0&&b>=0) return 0*puts("Zero");
    if(a<0&&(b-a)%2==0) puts("Negative");
    else puts("Positive");
    return 0;
}

B – Box and Ball

题意:

给你n个箱子,该开始只有一号箱子里有白球,其他箱子里都是黑球,然后你会进行 m次操作,每次操作你会从a_i箱子中随机取出一个球放到b_i中去…询问最后有多少个箱子可能有球.

分析:

我们记录每个箱子中球的数量和是否可能有红球,然后我们取球就有几种情况:
1. 我们从可能有红球的箱子里取出一个球,那么它可红可白,然后我们把他放到b_i中,那么b_i中也可能有有红球了..
2. 我们从可能有红球但只有一个球的箱子里取出一个球,那么它只能红,所以它之后就没有红球了,然后吧a_i的标记删掉
3. 我们从没有红球的箱子里取球,那么直接取就好了…
以上的步骤都要维护数量,最后统计个数就好了.

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define P pair<int,int>
const LL inf = 0x3f3f3f3f;
const LL mod = 1e9+7;
const LL N = 1e5+10;
template <typename tp> inline void read(tp &x)
{
    x=0;char c=getchar();int f=0;
    for(;c>'9'||c<'0';f|=(c=='-'),c=getchar());
    for(;c<='9'&&c>='0';x=(x<<3)+(x<<1)+c-'0',c=getchar());
    if(f) x=-x;
}
int n,m,ans;
int from,to,now[N],q[N];
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++) q[i]=1; now[1]=1;
    for(int i=1;i<=m;i++)
    {
        read(from),read(to);
        if(q[from]==1&&now[from]==1) now[from]=0,now[to]=1;
        else if(now[from]==1) now[to]=1;
        q[from]--,q[to]++;
    }
    for(int i=1;i<=n;i++) if(now[i]) ans++;
    printf("%d\n",ans);
    return 0;
}

C – Knot Puzzle

题意:

有一个n段绳子首尾相连的长绳,然后我们需要解开这个绳子,我们每次可以解开一条长度大于k的绳子问,能否解开所有绳子…

分析:

已知我们最后解开的一定是两个短绳的相连长绳,然后我们找到一对相邻的短绳长度大于k,就好了,接下来爱怎么解怎么解…

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define P pair<int,int>
const LL inf = 0x3f3f3f3f;
const LL mod = 1e9+7;
const LL N = 1e5+10;
template <typename tp> inline void read(tp &x)
{
    x=0;char c=getchar();int f=0;
    for(;c>'9'||c<'0';f|=(c=='-'),c=getchar());
    for(;c<='9'&&c>='0';x=(x<<3)+(x<<1)+c-'0',c=getchar());
    if(f) x=-x;
}
LL n,m,flag,len[N];
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++) read(len[i]);
    for(int i=1;i<n;i++) if(len[i]+len[i+1]>=m) {flag=i;break;}
    if(flag==0) return 0*puts("Impossible");
    puts("Possible");
    for(int i=1;i<flag;i++) printf("%d\n",i);
    for(int i=n-1;i>flag;i--) printf("%d\n",i);
    printf("%lld\n",flag);
    return 0;
}

D – Stamp Rally

题意:

给你一个无向图,然后给出m条询问,每次询问你从两个点出发,一共走过k个点需要消耗的最小编号….

分析:

我们看到这道题目,直接想到的是二分,我们二分最大的边的序号,然后我们从两个点出发把能走到的点的并集合起来,然后如果数目超过需要的个数,就是可行的值…
但是我们发现直接这样搜一遍是O(n)的,所以我们需要一个更快的方法,我们我们先向建最小生成树那样建出一颗新的树,然后我们对于每一条边我们建一个新的点去连两个并查集的根,这样子建出来的树,根一定比任何叶子要大,然后我们对于每个二分值,然后直接从叶子节点往上面倍增,然后最后可以到达的点的子树大小就是可以到的边的大小…

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define P pair<int,int>
const LL inf = 0x3f3f3f3f;
const LL mod = 1e9+7;
const LL N = 1e5+10;
template <typename tp> inline void read(tp &x)
{
    x=0;char c=getchar();int f=0;
    for(;c>'9'||c<'0';f|=(c=='-'),c=getchar());
    for(;c<='9'&&c>='0';x=(x<<3)+(x<<1)+c-'0',c=getchar());
    if(f) x=-x;
}
int n,m,q,fa[N*4],tot,val[N*4],num[N*4];
int F[N*4][25];P son[N*4];
int find(int now) {return fa[now]==now?now:fa[now]=find(fa[now]);}
void dfs(int now,int fath)
{
    F[now][0]=fath;
    for(int i=1;i<=22;i++) F[now][i]=F[F[now][i-1]][i-1];
    if(son[now].first==0) return;
    dfs(son[now].first,now),dfs(son[now].second,now);
}
int Val(int now,int maxk)
{
    for(int i=20;i>=0;i--) 
        if(val[F[now][i]]<=maxk) 
            now=F[now][i];
    return now;
}
int main()
{
    val[0]=inf;
    read(n),read(m);tot=n;
    for(int i=1;i<=n+m+10;i++) fa[i]=i;
    for(int i=1;i<=n;i++) num[i]=1;
    for(int i=1,u,v;i<=m;i++)
    {
        read(u),read(v);
        if(find(u)!=find(v))
        {

            val[++tot]=i;num[tot]=num[fa[u]]+num[fa[v]];
            son[tot].first=fa[u];
            son[tot].second=fa[v];
            fa[fa[u]]=tot,fa[fa[v]]=tot;
        }
    }
    dfs(tot,tot);read(q);
    for(int i=1,from,to,k;i<=q;i++)
    {
        read(from),read(to),read(k);
        int l=n+1,r=tot;
        while(l<r)
        {
            int mid=(l+r)>>1,Num=0;
            int ll=Val(from,val[mid]);
            int rr=Val(to,val[mid]);
            if(ll==rr) Num=num[ll];
            else Num=num[ll]+num[rr];
            if(Num>=k) r=mid;
            else l=mid+1;
        }
        printf("%d\n",val[l]);
    }
    return 0;
}

E – Candy Piles

题意:

给出n堆糖果,两个人进行博弈,每次一个人可以吃掉最大的一堆糖或者是从剩下的每一堆中吃一个糖,吃最后一个糖的人输,问谁会赢…

分析:

我们先把先给所有的糖果从大到小排序,然后我们发现每次相当于去掉第一行或者第一列…然后我们对于这个图进行操作,我们假设(i,j)表示现在前i行和前j列已经被取了,然后轮到我们抉择我们…
接下来我们找一个图进行手算操作,找规律…(i,j)=0仅当(i+1,j)=(i,j+1)=1(太烦了,自己搞)
然后有一个结论,(i,j)=(i-1,j-1)
最后怎么算随便你…

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define P pair<int,int>
const LL inf = 0x3f3f3f3f;
const LL mod = 1e9+7;
const LL N = 1e5+10;
template <typename tp> inline void read(tp &x)
{
    x=0;char c=getchar();int f=0;
    for(;c>'9'||c<'0';f|=(c=='-'),c=getchar());
    for(;c<='9'&&c>='0';x=(x<<3)+(x<<1)+c-'0',c=getchar());
    if(f) x=-x;
}
int n,x[N],zz,mm;
bool cmp(int a,int b){return a>b;}
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(x[i]);
    sort(x+1,x+n+1,cmp);
    for(int i=0;i<=n;i++) if(x[i+2]<=i+1) {mm=i;break;}
    for(int i=1;i<=n;i++) if(x[i]>mm) zz=i;
    if((x[mm+1]-mm)%2==1&&(zz-mm)%2==1) puts("Second");
    else puts("First");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注