In mathematics you don't understand things, you just get used to them.

动态 书籍 杂项 关于 友链

「ABC 193A」Discount

Link.

略。

#include<cstdio>
int main()
{
    int a,b;
    scanf("%d %d",&a,&b);
    printf("%.2f\n",(1.0-(double)b/(double)a)*100.0);
    return 0;
}

「ABC 193B」Play Snuke

Link.

排序。

#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
    int tim,pay,ps;
}nodes[100010];
bool cmp(node one,node ano)
{
    return one.pay<ano.pay;
}
int ans=-1;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)    scanf("%d %d %d",&nodes[i].tim,&nodes[i].pay,&nodes[i].ps);
    sort(nodes+1,nodes+n+1,cmp);
    for(int i=1;i<=n;++i)
    {
        if(((int)((double)nodes[i].tim-0.5)+1)<nodes[i].ps)
        {
            ans=nodes[i].pay;
            break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

「ABC 193C」Unexpressed

Link.

可以容斥，也可以暴力枚举 std::set 去重。

#include<set>
#include<iostream>
#define int long long
using namespace std;
set<int> app;
signed main()
{
    int n,ians=0;
    cin>>n;
    for(int i=2;i*i<=n;++i)
    {
        for(int j=i*i;j<=n;j*=i)
        {
            if(!app.count(j))
            {
                ++ians;
                app.insert(j);
            }
        }
    }
    cout<<n-ians;
    return 0;
}

「ABC 193D」Poker

Link.

开个答案+单位贡献的结构体，然后模拟。

#include<iostream>
#include<iomanip>
using namespace std;
#define int long long
#define ID(c) ((c)-'0')
int k,num[20];
char s[20],t[20];
struct node
{
    int iths[20],sum,c[20];
    int spow(int fur)
    {
        int res=1;
        for(int i=1;i<=fur;++i)    res*=10;
        return res;
    }
    void getscor(char x[])
    {
        for(int i=1;i<=4;++i)    ++c[ID(x[i])];
        for(int i=1;i<=9;++i)
        {
            iths[i]=i*spow(c[i]);
            sum+=iths[i];
        }
    }
    void Op(int pos,int delta)
    {
        c[pos]+=delta;
        sum-=iths[pos];
        if(~delta)    iths[pos]*=10;
        else    iths[pos]/=10;
        sum+=iths[pos];
    }
}tak,aok;
signed main()
{
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
    cin>>k>>(s+1)>>(t+1);
    for(int i=1;i<=9;++i)    num[i]=k;
    for(int i=1;i<=4;++i)    --num[ID(s[i])],--num[ID(t[i])];
    tak.getscor(s);
    aok.getscor(t);
    int winans=0,allans=0;
    for(int i=1;i<=9;++i)
    {
        for(int j=1;j<=9;++j)
        {
            tak.Op(i,1);
            aok.Op(j,1);
            if(tak.sum>aok.sum)
            {
                if(i^j)    winans+=num[i]*num[j];
                else    winans+=num[i]*(num[j]-1);
            }
            tak.Op(i,-1);
            aok.Op(j,-1);
        }
    }
    for(int i=1;i<=9;++i)
    {
        for(int j=1;j<=9;++j)
        {
            if(i^j)    allans+=num[i]*num[j];
            else    allans+=num[i]*(num[j]-1);
        }
    }
    cout<<fixed<<setprecision(6)<<(double)winans/(double)allans<<endl;
    return 0;
}

「ABC 193E」Oversleeping

Link.

开始想到计算几何去了，打了很久。

实际上因为 $500$ 的范围，你可以直接枚举余数然后 exCRT 合并。

#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=LONG_LONG_MAX;
namespace NumbTheo
{
    LL ftimes(LL bas,LL fur,LL mod)
    {
        LL res=0;
        while(fur)
        {
            if(fur&1)    res=(res+bas)%mod;
            bas=(bas+bas)%mod,fur>>=1;
        }
        return res;
    }
    LL exGCD(LL one,LL ano,LL &x,LL &y)
    {
        if(ano==0)    return (x=1,y=0,one);
        else
        {
            LL tmp=exGCD(ano,one%ano,y,x);
            y-=(one/ano)*x;
            return tmp;
        }
    }
    LL exCRT(LL n,LL one[],LL ano[])
    {
        LL x,y,res=one[1],M=ano[1];
        for(int i=2;i<=n;++i)
        {
            LL a=M,b=ano[i],c=(one[i]-res%b+b)%b,tmp=exGCD(a,b,x,y),d=b/tmp;
            if(c%tmp)    return -1;
            x=ftimes(x,c/tmp,d);
            res+=x*M,M*=d,res=(res%M+M)%M;
        }
        return (res%M+M)%M;
    }
};
int t;
LL one[10],ano[10],ans;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        LL X,Y,P,Q;
        scanf("%lld %lld %lld %lld",&X,&Y,&P,&Q);
        ans=INF;
        for(LL i=X;i<X+Y;++i)
        {
            for(int j=P;j<P+Q;++j)
            {
                using namespace NumbTheo;
                one[1]=i,ano[1]=((X+Y)<<1),one[2]=j,ano[2]=P+Q;
                LL tmp=exCRT(2,one,ano);
                if(~tmp)    ans=min(ans,tmp);
            }
        }
        if(ans==INF)    printf("infinity\n");
        else    printf("%lld\n",ans);
    }
    return 0;
}

「ABC 193F」Zebraness

Link.

把 $i+j$ 为奇数的地方反转一下，然后连边求最小割。

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
#define getID(x,y) (((x)-1)*n+(y))
namespace MaxFlow
{
    queue<int> q;
    const LL INF=1e9;
    int S,T,head[10010],Cur[10010],cntot=1,all,vis[10010];
    LL dep[10010];
    struct Edge
    {
        int to,nxt;
        LL c;
        Edge(int A=0,int B=0,LL C=0){to=A,nxt=B,c=C;}
    }as[500010];
    bool bfs()
    {
        for(int i=1;i<=all;++i)    vis[i]=0,dep[i]=INF;
        q.push(S),dep[S]=0,vis[S]=1;
        while(!q.empty())
        {
            int now=q.front();
            q.pop(),vis[now]=0;
            for(int i=head[now];i;i=as[i].nxt)
            {
                int y=as[i].to;
                LL c=as[i].c;
                if(c&&dep[y]>dep[now]+1)
                {
                    dep[y]=dep[now]+1;
                    if(!vis[y])    q.push(y),vis[y]=1;
                }
            }
        }
        return dep[T]<INF;
    }
    LL dfs(int x,LL lav)
    {
        if(x==T)    return lav;
        LL used=0;
        vis[x]=1;
        for(int &i=Cur[x];i;i=as[i].nxt)
        {
            int y=as[i].to;
            LL c=as[i].c;
            if(c&&dep[y]==dep[x]+1&&!vis[y])
            {
                LL tmp=dfs(y,min(lav-used,c));
                as[i].c-=tmp,as[i^1].c+=tmp,used+=tmp;
                if(lav==used)    break;
            }
        }
        if(used<lav)    dep[x]=INF;
        vis[x]=0;
        return used;
    }
    LL Dinic()
    {
        LL res=0;
        while(bfs())
        {
            for(int i=1;i<=all;++i)    vis[i]=0,Cur[i]=head[i];
            res+=dfs(S,INF);
        }
        return res;
    }
}using namespace MaxFlow;
int n;
int rop()
{
    char res=getchar();
    while((res^'B')&&(res^'W')&&(res^'?'))    res=getchar();
    if(res=='?')    return -1;
    else if(res=='B')    return 1;
    else    return 0;
}
void addEdge(int one,int ano,int lav)
{
    as[++cntot]=Edge(ano,head[one],lav);
    head[one]=cntot;
    as[++cntot]=Edge(one,head[ano],0);
    head[ano]=cntot;
}
int main()
{
    scanf("%d",&n),all=n*n;
    S=(++all),T=(++all);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            int x=rop();
            if(~x)
            {
                if((i+j)&1)    x^=1;
                if(x)    addEdge(S,getID(i,j),INF);
                else    addEdge(getID(i,j),T,INF);
            }
        }
    }
    for(int i=1;i<n;++i)
    {
        for(int j=1;j<=n;++j)    addEdge(getID(i,j),getID(i+1,j),1),addEdge(getID(i+1,j),getID(i,j),1);
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<n;++j)    addEdge(getID(i,j),getID(i,j+1),1),addEdge(getID(i,j+1),getID(i,j),1);
    }
    printf("%lld\n",2*n*(n-1)-Dinic());
    return 0;
}

data structures number theory flows

Note -「virtual tree」shorter vrt
上一篇 «
Solution -「洛谷 P7395」「CoE-I 2021C」弹珠游戏
» 下一篇