首页 > 其他分享 >NWERC 2013

NWERC 2013

时间：2022-10-24 15:37:09浏览次数：65  
标签：ch return int NWERC long ll 2013 define


B Battle for Silver

容易发现答案最多有4个点，枚举所有4个点一下的完全图。

#include<bits/stdc++.h> 
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma
#define
#define
#define
#define
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
int S[1000],n,m;
bool b[500][500];
int u[1000],v[1000];
int main()
{
//  freopen("B.in", "r", stdin);
    while(cin>>n>>m) {
        For(i,n) For(j,n) b[i][j]=0;
        int ans=0;
        For(i,n) S[i]=read(), gmax(ans,S[i])
        For(i,m) {
            u[i]=read(),v[i]=read();
            b[u[i]][v[i]]=b[v[i]][u[i]]=1;
            gmax(ans,S[u[i]]+S[v[i]])
        }
        For(i,m) {
            For(j,n) if (u[i]!=j && v[i] != j &&b[u[i]][j] && b[v[i]][j] ){
                gmax(ans,S[j] + S[u[i]] + S[v[i]] )
            }
            For(j,m) if (u[i]!=u[j] && v[i] != u[j] && u[i]!=v[j] && v[i] != v[j] ){
                if (b[u[i]][v[j]] &&b[u[j]][v[i]] && b[u[i]][u[j]]  && b[v[i]][v[j]] ) {
                    gmax(ans,S[u[j]] + S[v[j]] + S[u[i]] + S[v[i]] )

                }
            }
        }
        cout<<ans<<endl;

    }   

    return 0;
}

C Card Trick

概率dp

G Grachten

#include<bits/stdc++.h> 
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma
#define
#define
#define
#define
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
ll gcd(ll a,ll b) {if (!b) return a;return gcd(b,a%b);}
int main()
{
    ll x,y,z;
//  freopen("G.in", "r", stdin);
    while(cin>>x>>y>>z) {
        ll p1=x*z;
        ll p2=z-y;
        ll g=gcd(p1,p2);
        p1/=g,p2/=g;
        p1-=x*p2;
        cout<<p1<<'/'<<p2<<endl;
    }   

    return 0;
}

I Infix to Prefix

显然我们可以区间dpO(n3)暴力转移
然后这样就可以过了。

#include<bits/stdc++.h> 
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma
#define
#define
#define
#define
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
#define
string Filename="I";
int n;
char s[MAXN];
ll dpmax[MAXN][MAXN],dpmin[MAXN][MAXN];
bool vis[MAXN][MAXN],valid[MAXN][MAXN];
bool calc(int i,int j) {
    if (i>j) return 0;
    if (vis[i][j]) return valid[i][j];
    vis[i][j]=1;
    dpmax[i][j]=-INF;
    dpmin[i][j]=INF;

    if (s[i]=='+') {
        Fork(k,i+1,j-1) {
            if (calc(i+1,k) && calc(k+1,j)) {
                gmax(dpmax[i][j] , dpmax[i+1][k] + dpmax[k+1][j] );
                gmin(dpmin[i][j] , dpmin[i+1][k] + dpmin[k+1][j] );
                valid[i][j]=1;
            }
        }
    }
    if (s[i]=='-') {
        if (calc(i+1,j)) {
            gmax(dpmax[i][j] , - dpmin[i+1][j]  );
            gmin(dpmin[i][j] , - dpmax[i+1][j]  );
            valid[i][j]=1;
        }
        Fork(k,i+1,j-1) {
            if (calc(i+1,k) && calc(k+1,j)) {
                gmax(dpmax[i][j] , dpmax[i+1][k] - dpmin[k+1][j] );
                gmin(dpmin[i][j] , dpmin[i+1][k] - dpmax[k+1][j] );
                valid[i][j]=1;
            }
        }
    }
    return valid[i][j];
}
int main()
{
//  freopen((Filename+".in").c_str(), "r", stdin);
    while(scanf("%s",s+1)==1) {
        n=strlen(s+1);
        MEM(vis) MEM(valid)
        For(i,n) if (isdigit(s[i])) {
            ll p=0;
            Fork(j,i,min(i+8,n) ) {
                if (!isdigit(s[j])) break;
                p=p*10+s[j]-'0';
                dpmax[i][j]=dpmin[i][j]=p;
                valid[i][j]=vis[i][j]=1;
                if (j==i && s[i]=='0') break;
            }
        }
        calc(1,n);
        cout<<dpmin[1][n]<<' '<<dpmax[1][n]<<endl;
    } 


    return 0;
}

J Jingle Balls

考虑先把树清空在往里扔苹果，计算放同等数量苹果时和原来的非重合数个数（只考虑完空树中填苹果）
根据限制条件，假设现在某个子树要放k个苹果，容易发现最多只有2种情况。
同时由于每次节点数都会变为原来的一半，最多只要计算log500 层，就剩0个或1个苹果，可以特判跳出。
答案=往空树里填了几次苹果

#include<bits/stdc++.h> 
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma
#define
#define
#define
#define
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
string Filename="J";
char s[10000];
int tot=0,n;
int pre[10000];
int a[10000];
bool fl=1;
int ans=0;
int f[5310][2310];
int Abs(int x){return max(-x,x);
}
bool dfs(int l,int r,int k) {
    if (!k) {
        f[l][k]=0; return 1;
    }

    ++l,--r;    
    if (l==r) {
        int pson=k;
        if (k==1) {
            f[l-1][k]=0;
            return 1;       
        } else if (k==0) {
            f[l-1][k]=1;
            return 1;       
        }
        return 0;
    }
    else if (r==l-1) {
        int pson=k;
        if (k==0) {
            f[l-1][k]=0;
            return 1;       
        } else if (k==1) {
            f[l-1][k]=1;
            return 1;       
        }
        return 0;
    }

    int pl=pre[l],pr=pre[r];

    f[l-1][k]=INF;
    if (dfs(l,pl,k>>1)&& dfs(pr,r,k-(k>>1) )) {
        gmin(f[l-1][k],f[l][k>>1]+f[pr][k-(k>>1)]);
    }
    int side=k>>1;
    if (side!=k-side)
        if (dfs(l,pl,k-side)&& dfs(pr,r,side) ) {
            gmin(f[l-1][k],f[l][k-side]+f[pr][side]);
        }
    return f[l-1][k]!=INF;

}
stack<int> st;
int main()
{
//  freopen((Filename+".in").c_str(), "r", stdin);
    while(scanf("%s",s+1)!=EOF) {
        n=strlen(s+1); tot=0;
        a[0]=0;
        For(i,n) {
            a[i]=a[i-1]+(s[i]=='B');
            if (s[i]=='B') ++tot;
            else if (s[i]=='(') st.push(i);
            else if (s[i]==')'){
                int p=st.top();st.pop();
                pre[i]=p,pre[p]=i;
            }
        }
        fl=dfs(1,n,tot);
        if (!fl) puts("impossible");
        else {
            printf("%d\n",f[1][tot]);
        }
    }
    return 0;
}


标签：ch,return,int,NWERC,long,ll,2013,define
From： https://blog.51cto.com/u_15724837/5789899

相关文章

  • IIS Community Newsletter June 2013
    Announcements​Windows2012ServerR2previewreleasedWindowsServer2012R2providesawiderangeofnewandenhancedfeaturesandcapabilitiesspanningserv......
  • 20201302姬正坤第五章学习笔记
    LINUX第五章定时器及时钟服务硬件定时器定时器是由时钟源和可编程计数器组成的硬件设备。时钟源通常是一个晶体振荡器，会产生周期性电信号，以精确的频率驱动计数器。使用......
  • 20201306吴龙灿第五章学习笔记
    Ⅰ知识点归纳一、硬件定时器定时器是由时钟源和可编程计数器组成的硬件设备。时钟源通常是一个晶体振荡器，会产生周期性电信号，以精确的频率驱动计数器。硬件定时器能够按......
  • 20201318李兴昕学习笔记八
    第五章：定时器及时钟服务知识点归纳总结：本章讨论了定时器和定时器服务；介绍了硬件定时器的原理和基于Intelx86的PC中的硬件定时器；讲解了CPU操作和中断处理；描述了Linux......
  • P4097 [HEOI2013]Segment
    题目链接P4097[HEOI2013]Segment题目描述要求在平面直角坐标系下维护两个操作：在平面上加入一条线段。记第\(i\)条被插入的线段的标号为\(i\)。给定一个数\(k\)，......
  • P2059 [JLOI2013] 卡牌游戏 题解
    一道不错的线性dp，带了点逆推。注意到如果我们设\(f_{i,j}\)表示前\(i\)轮过后\(j\)存活的概率，那么我们需要额外记录哪些人无了，否则无法转移。考虑这样一件事：无论......
  • [IOI2013]robots 机器人
    题目传送门思路简单题，设函数\(f_i\)表示当时间为\(i\)时是否能够收拾好所有玩具，则\(f_i\)显然是单调的。所以我们可以考虑二分。设我们当前二分到\(x\)，我们先把......
  • 数据集 | 以色列高中的巴格鲁特成绩（2013-2016）数据集
    下载数据集请登录爱数科该文件包含2013年至2016年之间1800多个不同学科的学校平均60,000等级的Bagrut成绩。1.字段描述2.数据预览3.字段诊断信息4.数据来源来源于Kaggle......
  • 20201302姬正坤Linux第四章学习笔记
    第四章并发编程一、并行计算导论1、顺序算法与并行算法在描述顺序算法中，常用一个begin-end代码块列出算法。该代码块中的所有步骤都是通过某个任务依次执行的。而并行......
  • 20201322陈俊池学习笔记7
    第四章并发编程4.1并行计算导论在早期，大多数计算机只有一个处理组件，称为处理器或中央处理器（CPU）。受这种硬件条件的限制，计算机程序通常是为串行计算编写的。要求解某个......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99