澳门威利斯人_威利斯人娱乐「手机版」

来自 威利斯人娱乐 2019-11-16 06:11 的文章
当前位置: 澳门威利斯人 > 威利斯人娱乐 > 正文

解题报告

Codeforces Round #305 (Div. 1) A.B.C 解题报告

A. Mike and Frog
枚举。
先是找循环,然后超级轻易得出三个两元一回方程,然后能够窥见解也有循环节的,所以最小的卓殊肯定出未来必然约束内,不然就前面也不或然现身。假使四个变量为x,y,周详分别为z1,z2。很明朗,两个的最小公倍数就是一个周期,所以如果枚举x的话,只需求枚举到z2就可以了。
细节超多。。错了好数13回。。竞赛中也跪了。。
代码如下:

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
using namespace std;
#define LL __int64
#define pi acos(-1.0)
#define root1 0, 1000001, 1
#define lson l, mid, rt<<1
#define rson mid 1, r, rt<<1|1
//#pragma comment(linker, "/STACK:1024000000")
const int mod=1e4 7;
const int INF=0x3f3f3f3f;
const double eqs=1e-3;
const int MAXN=600000 10;
int a[MAXN], c[20], ha[MAXN], vis[MAXN];
LL Cal(int x, int f)
{
        int i, cnt=0, tmp, tot, y, j;
        LL ans=0;
        for(i=2;i*i<=x;i  ){
                if(x%i==0){
                        while(x%i==0) x/=i;
                        c[cnt  ]=i;
                }
        }
        if(x!=1) c[cnt  ]=x;
        tot=1<

B. Mike and Feet 单调栈(或者线段树) 这题的大体思路很容易,就是找出每个数作为最小值的向左向右延伸的最大范围,那么这个范围之内的都有可能会以这个最小值作为最大值,于是用标记法标记前缀的最大值就可以了。 然后就是找延伸的范围了。弱只想到了万能的离散化 线段树的思路。也不算很麻烦,但是复杂度略高。还有一个更简单的方法是单调栈的思路。不止复杂度低,只有O(n),代码复杂度也低。用单调栈来保证栈内始终是递增的,所以栈底就是延伸的最大范围。在这里只贴个线段树的思路的,也是弱比赛的时候写的。 话说比赛的时候因为定义了两个n。。调试了将近一个小时。。。时间全浪费在这上面了。。。。 代码如下:

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
using namespace std;
#define LL __int64
#define pi acos(-1.0)
#define root 0, cnt-1, 1
#define lson l, mid, rt<<1
#define rson mid 1, r, rt<<1|1
//#pragma comment(linker, "/STACK:1024000000")
const int mod=1e4 7;
const int INF=0x3f3f3f3f;
const double eqs=1e-3;
const int MAXN=200000 10;
int dp[MAXN], b[MAXN], ans[MAXN], a[MAXN], c[MAXN], cnt, fro[MAXN], last[MAXN], n;
int Max[800000], Min[800000];
int BS(int x)
{
        int low=0, high=cnt-1, mid;
        while(low<=high){
                mid=low high>>1;
                if(c[mid]==x) return mid;
                else if(c[mid]>x) high=mid-1;
                else low=mid 1;
        }
}
void PushUp(int rt)
{
        Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
        Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);
}
void Update(int p, int x, int l, int r, int rt)
{
        if(l==r){
                Max[rt]=Min[rt]=x;
                return ;
        }
        int mid=l r>>1;
        if(p<=mid) Update(p,x,lson);
        else Update(p,x,rson);
        PushUp(rt);
}
int Query(int f, int ll, int rr, int l, int r, int rt)
{
        if(ll<=l&&rr>=r){
                if(f) return Max[rt];
                return Min[rt];
        }
        int mid=l r>>1, ans;
        if(f) ans=-1;
        else ans=n;
        if(f){
                if(ll<=mid) ans=max(ans,Query(f,ll,rr,lson));
                if(rr>mid) ans=max(ans,Query(f,ll,rr,rson));
        }
        else{
                if(ll<=mid) ans=min(ans,Query(f,ll,rr,lson));
                if(rr>mid) ans=min(ans,Query(f,ll,rr,rson));
        }
        return ans;
}
int main()
{
        int i, j, x;
        while(scanf("%d",&n)!=EOF){
                for(i=0;i=0;i--){
                        x=BS(a[i]);
                        if(x==0) last[i]=n;
                        else last[i]=Query(0,0,x-1,root);
                        Update(x,i,root);
                }
                memset(dp,0,sizeof(dp));
                memset(ans,0,sizeof(ans));
                int tmp;
                for(i=0;i=1;i--){
                        ans[i]=max(ans[i 1],dp[i]);
                }
                for(i=1;i<=n;i  ){
                        printf("%d ",ans[i]);
                }
                puts("");
        }
        return 0;
}

C. Mike and Foam 状压 容斥 这题只要想清楚一点就很简单了。。。就是5*10^5范围内的任意一个数的质因子的个数都不会超过6个。。只要想到了这点,就很简单了,状压一下再容斥一下乱搞搞就解决了。 代码如下:

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
using namespace std;
#define LL __int64
#define pi acos(-1.0)
#define root1 0, 1000001, 1
#define lson l, mid, rt<<1
#define rson mid 1, r, rt<<1|1
//#pragma comment(linker, "/STACK:1024000000")
const int mod=1e4 7;
const int INF=0x3f3f3f3f;
const double eqs=1e-3;
const int MAXN=600000 10;
int a[MAXN], c[20], ha[MAXN], vis[MAXN];
LL Cal(int x, int f)
{
        int i, cnt=0, tmp, tot, y, j;
        LL ans=0;
        for(i=2;i*i<=x;i  ){
                if(x%i==0){
                        while(x%i==0) x/=i;
                        c[cnt  ]=i;
                }
        }
        if(x!=1) c[cnt  ]=x;
        tot=1<

Round #305 (Div. 1) A.B.C 解题报告 A. Mike and Frog 枚举。 先是找循环,然后十分轻便得出一个两元二遍方程,然后能够窥见解也可能有轮回节...

Codeforces Round #305 (Div. 1) B. Mike and Feet

Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to n from left to right. i-th bear is exactly ai feet high.

图片 1

A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strengthof a group is the minimum height of the bear in that group.

Mike is a curious to know for each x such that 1 ≤ x ≤ n the maximum strength among all groups of size x.

Input

The first line of input contains integer n (1 ≤ n ≤ 2 × 105), the number of bears.

The second line contains n integers separated by space, a1, a2, ..., an (1 ≤ ai ≤ 109), heights of bears.

Output

Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.

Sample test(s) input

10
1 2 3 4 5 4 3 2 1 6

output

6 4 4 3 3 2 2 1 1 1

那题能够用单调栈做,维护三个栈,记录minmum(该间距的最小值卡塔尔国和count(区间的总参谋长度卡塔尔。

 

#include
#include
#include
#include
#include
using namespace std;
#define maxn 200060
int ans[maxn];
struct node{
 int count,minmum;
}stack[maxn];
int main()
{
 int n,m,i,j,top,count,b;
 while(scanf(%d,&n)!=EOF)
 {
  memset(ans,0,sizeof(ans));
  top=0;
  for(i=1;i<=n;i  ){
   scanf(%d,&b);
   count=0;
   while(top>0 && stack[top].minmum>=b){
    stack[top].count =count;
    count=stack[top].count;
    if(ans[count]0){
    stack[top].count =count;
    count=stack[top].count;
    if(ans[count]                /*这里算出来的ans[i]是连续长度为i的区间的最小值,但这个最小值是所有连续长度为i的区间长度的最大值,下面如果ans[i 1]比ans[i]大,那么ans[i]可以更新为ans[i 1],因为如果i 1个连续数区间的最小值的最大值是b,那么去掉一个数,一定可以做到长度为i的连续数区间的最大值是b。*/

  for(i=n;i>=2;i--){
   if(ans[i]>ans[i-1]){
    ans[i-1]=ans[i];
   }
  }
  for(i=1;i<=n-1;i  ){
   printf(%d ,ans[i]);
  }
  printf(%d
,ans[i]);
 }
 return 0;
}

 

Round #305 (Div. 1) B. Mike and Feet Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standin...

Codeforces Round #311 (Div. 2) A,B,C,D,E

A. Ilya and Diplomas

思路:水题了, 随随便便枚举一下,分景况讨论一下就OK了。

 

code:

 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 1000000
#define clr(x, y) memset(x, y, sizeof x)

using namespace std;

int rmina,rmaxa;
int rminb,rmaxb;
int rminc,rmaxc;
int n;

int main()
{
    scanf(%d, &n);
    scanf(%d%d%d%d%d%d, &rmina, &rmaxa, &rminb, &rmaxb, &rminc, &rmaxc);
    int d = n - rminb - rminc;
    if (d > rmaxa)
    {
        d = n - rmaxa - rminc;
        if (d > rmaxb)
        {
            d = n - rmaxa - rmaxb;
            printf(%d %d %d
, rmaxa, rmaxb, d);
        }
        else printf(%d %d %d
, rmaxa, d, rminc);
    }
    else printf(%d %d %d
, d, rminb, rminc);

    return 0;
}

B. Pasha and Tea

 

题意:风流倜傥共有w升水,有n个汉子和n个女子。每一种人都有三个有容积约束a[i]的双耳杯,每种男人分到的水体积相等,每种女面生到的水体积相等,且每一种男人分到的水是女子的二倍,问全数人能分到水的体量的最大值是有个别。

 

思路:设x为在总终状态下种种女不熟悉到的水的量,a代表女人的蝇头容积,b代表男子的蝇头容积,则有x = min(a,b/2,w/3*n),则 ans = x * 3* n

 

code :

 

#include 
#include 
#include 
#include 
#include 
#include 
#define clr(x, y) memset(x, y, sizeof x)
#define inf 1000000000
using namespace std;

const int maxn = 300005;

int a[maxn];
int n, w;

int main()
{
    scanf(%d%d, &n, &w);
    for (int i = 0; i < 2*n; i  ) scanf(%d, &a[i]);
    sort(a, a   2*n);
    double x0 = (double)w / (3*n);
    double x1 = (double)a[0];
    double x2 = (double)a[n] / 2;

    x0 = min(x0, x1);
    x0 = min(x0, x2);

    x0 = x0 * 3 * n;

    printf(%f
, x0);

    return 0;
}

 

C. Arthur and Table

 

题意:给三个有n个腿的台子,每一种腿有其尺寸li,同期移除某些腿须求耗费di的能量,当长度为最大值的腿的个数大于桌腿的总额的时候,桌子处于平稳状态,输入给出n,li,di问将案子形成平稳状态所急需的成本的能量的小小值。

 

思路:第生龙活虎即时上去料定是要去枚举最大尺寸的桌腿了,可是怎么着连忙的计量分明桌腿后完毕牢固状态所急需费用的能量呢? 那些能量包含两有个别,风姿罗曼蒂克部分是将长度超过当前正值枚举的桌腿的桌腿全部删掉所要求的能量,大器晚成部分是删掉使被枚举的尺寸的桌腿个数大于八分之四所要消耗的能量。 风流浪漫初叶笔者把全体的集中力全体都位于了单个的桌腿上,然后在寻思复杂度的时候怎么算都感到会晚点, 后来才注意到难题的key ------- di 的轻重唯有200, 能够依据di对桌脚实行分类, 然后从小到大来枚举di,难点就一挥而就了~~

 

code:

 

#include 
#include 
#include 
#include 
#include 
#include 
#define clr(x, y) memset(x, y, sizeof x)
#define inf 1000000000
using namespace std;

const int maxn = 100005;

int n;
int L[maxn];
int D[maxn];

int sum[maxn];
int cnt[maxn];
int cnt_d[maxn];

struct pp
{
    int li, di;

    pp(int a = 0, int b = 0) : li(a), di(b) {}

} P[maxn];


bool cmp(pp A, pp B)
{
    return A.li > B.li;
}

int main()
{
    scanf(%d, &n);
    for (int i = 0; i < n; i  ) scanf(%d, &L[i]);
    for (int i = 0; i < n; i  ) scanf(%d, &D[i]);
    for (int i = 0; i < n; i  ) P[i] = pp(L[i],D[i]);

    clr(sum, 0);    clr(cnt, 0);    clr(cnt_d, 0);

    for (int i = 0; i < n; i  )
    {
        sum[L[i]]  = D[i];
        cnt[L[i]]   ;
        cnt_d[D[i]]   ;
    }

    sort(P, P   n, cmp);

    int coa, ss, cnta, ans;

    coa = 0;
    cnta = 0;
    ans = inf;

    for (int i = 0; i < n; i  )
    {
        ss = coa;
        int v = P[i].li;
        int j;
        for (j = i; j < n; j  )
        {
            if (P[j].li != v) break;
            cnt_d[P[j].di]--;
        }
        i = j-1;

        int nn = n - cnta;
        int cha;
        if (cnt[v] == 1) cha = nn - 1;
        else cha = nn - (cnt[v] - 1) * 2 - 1;
        for (int i = 1; i <= 200; i  )
        {
            if (cha > cnt_d[i])
            {
                ss  = cnt_d[i] * i;
                cha -= cnt_d[i];
            }
            else
            {
                if (cha >= 0) ss  = i * cha;
                break;
            }
        }
        ans = min(ans, ss);
        cnta  = cnt[v];
        coa  = sum[v];
    }

    printf(%d
, ans);

    return 0;
}

 

 

D. Vitaly and Cycle

 

 

题意:给出叁个无向图(图恐怕不联通卡塔 尔(阿拉伯语:قطر‎,问最少投入多少条边能够使图具备贰个奇环,并总结有多少种加边的办法。

 

思路: 标题其实不是很难,然而本人做的时候也是磨了浓厚才把标题给磨出来, 做法是那般的:首先有多个贵族都懂的事实:要结合奇环加入边的个数不会超越3条,然后再分景况探讨参预0,1,2,3条边的状态。

第黄金年代对图举行是非染色,在染色的还要总括每一种联通块中紫褐节点的个数, 还会有灰绿节点的个数,然后探究

Case 0: 假如存在三个联通块黑白染色不成功,则一定期存款在叁个奇环,当时所急需投入的边数就为0,其方案数一定为1。(假使有一条边的双边颜色是同样的则染色不成事卡塔 尔(英语:State of Qatar)

Case 1: 对于四个联通块,假设用一条边将八个黄褐点大概法国红点连起来,就会形成贰个奇环,所以就可以经过一同头所总结的每种联通块中黑白节点的个数飞速的总括出来。

Case 2: 假若每一个联通块都以1个顶峰大概多少个极点,则用2条边就能够产生环,这种就总括一下三个点的连通块和五个点的衔接块各有多少个再用整合数学搞生龙活虎搞就能够了。

Case 3: 全部都是独立点的景况, 从中随便取三个点就足以了~~~

 

ps: 黑白染色其实一贯跑叁回dfs(or bfs卡塔 尔(阿拉伯语:قطر‎ 就能够了, 笔者太年富力强的先跑了一个生成树,然后则染色,其实未有需要~。

 

code:

 

#include 
#include 
#include 
#include 
#include 
#include 
#define clr(x, y) memset(x, y, sizeof x)
#define inf 1000000000
using namespace std;

const int maxn = 200005;

vector G[maxn];

struct edge
{
    int st,ed;
    bool flag;
} E[maxn];

int n, m;
int par[maxn];
int col[maxn];
int white[maxn];
int black[maxn];
int ta;

void init(int n_)
{
    for(int i = 0; i <= n_; i  ) par[i] = i;
}

int Find(int x)
{
    if (x == par[x]) return x;
    return par[x] = Find(par[x]);
}
void unit(int x, int y)
{
    x = Find(x);
    y = Find(y);
    if (x == y) return ;
    par[y] = x;
}
bool same(int x, int y)
{
    return Find(x) == Find(y);
}

void dfs(int u, int &wh, int &bl)
{
    for(int i = 0; i < G[u].size(); i  )
    {
        int v = G[u][i];
        if (col[v] != -1) continue;
        col[v] = col[u]^1;
        col[v] == 0? wh   : bl  ;
        dfs(v, wh, bl);
    }
}

int main()
{
    scanf(%d%d, &n, &m);
    int st, ed;
    for (int i = 0; i < m; i  )
    {
        scanf(%d%d, &E[i].st, &E[i].ed);
        E[i].flag = false;
    }
    init(n);
    for (int i = 0; i < m; i  )
    {
        if (!same(E[i].st, E[i].ed))
        {
            unit(E[i].st, E[i].ed);
            G[E[i].st].push_back(E[i].ed);
            G[E[i].ed].push_back(E[i].st);
            E[i].flag = true;
        }
    }
    clr(col, -1);   clr(white, 0);  clr(black, 0);  ta = 0;
    for (int i = 1; i <= n; i  )
    {
        if (col[i] == -1)
        {
            int wh = 1;
            int bl = 0;
            col[i] = 0;
            dfs(i, wh, bl);
            white[ta] = wh;
            black[ta  ] = bl;
        }
    }
    for (int i = 0; i < m; i  )
    {
        if (E[i].flag == true) continue;
        if (col[E[i].st] == col[E[i].ed])
        {
            printf(0 1
);
            return 0;
        }
    }
    long long w = 0;
    for (int i = 0; i < ta; i  )
    {
        if (white[i] > 1) w  = (long long)white[i]*(white[i]-1)/2;
        if (black[i] > 1) w  = (long long)black[i]*(black[i]-1)/2;
    }
    if (w > 0)
    {
        printf(1 %lld
, w);
        return 0;
    }
    int cnt = 0;
    int tmp = n;
    for (int i = 0; i < ta; i  )
    {
        if (white[i] black[i] > 1) cnt  ;
    }
    for (int i = 0; i < ta; i  )
    {
        if (white[i] black[i] > 1)
        {
            cnt--;
            tmp -= 2;
            w  = tmp;
            w  = 2*cnt;
        }
        else
        {
            tmp --;
            w  = cnt;
        }
    }
    if (w > 0)
    {
        printf(2 %lld
, w);
        return 0;
    }
    w  = (long long)n*(n-1)*(n-2)/6;
    printf(3 %lld
, w);
    return 0;

}

 

E. Ann and Half-Palindrome

 

题意: 首先标题定义了三个半回文串:八个串是半回文串,当且仅当,这么些中间轴左侧的奇数位置上的字符与其对称地点上的字符相符,标题给出一个串s,和整数k让您求出s的具有半回文子串中字典序第k大的串,s的尺寸是5000。

 

思路:那道难题做起来也可谓是曲折满满啊, 一开头听刘神说是暴力,就和好敲了三个最最强力的做法,尼玛啊O(n^3卡塔尔的办法你怕不怕,然后风流倜傥算确定超时啊,就在想怎么来优化,感到枚举子串的地点未有怎么可优化的了, 就在想判回文的地点有未有啥样能够更加快的章程,没想出来(依旧太弱了卡塔 尔(英语:State of Qatar),然后刘神告诉小编说用区间dp的思想随意预管理一下就能够了,立即清醒,立刻又去改了一发,开掘超内存->___->,然后刘神有告诉笔者说用动态字典树啊,然后自个儿就去改了字典树,开掘T了~~, 豆蔻年华看刘神的架子才察觉字典树的插入是O(n卡塔 尔(阿拉伯语:قطر‎的,可是他没插入三个就一定于插入了独具的以插入串起来的前缀子串,所以在枚举子串的时候独有枚举头就能够了~,又改了一发最终才过...

 

中间字典树的各类节点都多维护八个域用来存,其子树中有稍许个半回文串,之后找第K大的串就用相仿平衡树上dfs查找有个别节点的沉思不停的搜寻左右子树就能够了,当中还大概有一点点小的底细须要潜心~~~

 

code:

 

#include 
#include 
#include 
#include 
#include 
#include 
#define clr(x, y) memset(x, y, sizeof x)
#define inf 1000000000
using namespace std;

string s;
int k;
vector vv;

int dp[5005][5005];

int dfs(int i, int j)
{
    if (i == j) return dp[i][j] = 1;
    if (j < i) return dp[i][j] = 1;

    if (dp[i][j] != -1) return dp[i][j];
    if (dfs(i 2,j-2) && s[i] == s[j]) return dp[i][j] = 1;
    return dp[i][j] = 0;
}

class Trie
{
public:
    int flag;
    int num;
    Trie* next[2];
    Trie()
    {
        flag=0;
        num=0;
        next[0] = next[1] = 0;
    }
} * root;

int dfs(Trie * p)
{
    if (!p) return 0;
    p->num  = p->flag;
    p->num  = dfs(p->next[0]);
    p->num  = dfs(p->next[1]);
    return p->num;
}
string solve(Trie * p, int k)
{
    Trie * lson = p->next[0], *rson = p->next[1];;
    int lnum, rnum;
    if (lson == 0) lnum = 0;
    else lnum = lson->num;
    if (rson == 0) rnum = 0;
    else rnum = rson->num;

    if (p->flag >= k) return ;
    else if (lnum   p->flag >= k) return a   solve(lson,k-p->flag);
    else return b   solve(rson, k - lnum - p->flag);
}

void Trie_insert(int st, int ed)
{
    Trie* p= root;
    for(int i = st; i < ed; i  )
    {
        int index;
        if (s[i] == 'a') index = 0;
        else index = 1;

        if(!p->next[index]){
            p->next[index]=new Trie;
        }
        p=p->next[index];
        if (dfs(st,i)) p->flag  ;
    }
}

int main()
{
    cin>>s>>k;
    int len = s.length();
    clr(dp, -1);
    root = new Trie();
    for (int i = 0; i < len; i  )
    {
        Trie_insert(i, len);
    }
    dfs(root);
    cout<< solve(root,k) < 补完了一场题目,给自己加个油~~ 

Round #311 (Div. 2) A,B,C,D,E A. Ilya and Diplomas 思路:水题了, 随随意便枚举一下,分情状探讨一下就OK了。 code: #include #include #include #...

本文由澳门威利斯人发布于威利斯人娱乐,转载请注明出处:解题报告

关键词: 澳门威利斯人