noip2017day1

P3951 小凯的疑惑

题目描述

小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。

输入输出格式

输入格式：

两个正整数

输出格式：

一个正整数

输入输出样例

输入样例#1：复制

3 7

输出样例#1：复制

说明

【输入输出样例 1 说明】

小凯手中有面值为

题解：a*b-a-b

P3952 时间复杂度

题目描述

小明正在学习一种新的编程语言 A++，刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序，于是你的机会来啦！下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++语言的循环结构如下：

F i x y
    循环体
E

其中F i x y表示新建变量

“E”表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。

注：本题中为了书写方便，在描述复杂度时，使用大写英文字母“O”表示通常意义下“Θ”的概念。

输入输出格式

输入格式：

输入文件第一行一个正整数

接下来每个程序的第一行包含一个正整数 $串表示这个程序的复杂度，O(1)表示常数复杂度，O(n^w)表示复杂度为 n^wnw ，其中w是一个小于100的正整数（输入中不包含引号），输入保证复杂度只有O(1)和O(n^w) 两种类型。$

接下来

程序行若以E开头，则表示循环体结束。

输出格式：

输出文件共

注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出 ERR。

输入输出样例

输入样例#1：复制

8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E

输出样例#1：复制

Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

说明

【输入输出样例解释1】

第一个程序

第二个程序

第三个程序有一个 F 开启循环却没有 E 结束，语法错误。

第四个程序二重循环，

第五个程序两个一重循环，

第六个程序第一重循环正常，但第二重循环开始即终止（因为

第七个程序第一重循环无法进入，故为常数复杂度。

第八个程序第二重循环中的变量

【数据规模与约定】

对于 $30\%30% 的数据：不存在语法错误，数据保证小明给出的每个程序的前 L/2 行一定为以 F 开头的语句，第L/2+1 行至第 LL 行一定为以 EE 开头的语句， L≤10 ，若 x、y 均为整数， xx 一定小于 yy ，且只有 yy有可能为 nn 。$

对于 $50\%50% 的数据：不存在语法错误，L≤100 ，且若 x 、 yy均为整数， xx一定小于 y ，且只有 y 有可能为 n 。$

对于 $70\%70% 的数据：不存在语法错误，L≤100 。$

对于 $100\%100% 的数据：L≤100 。$

c_str()函数返回一个指向正规C字符串的指针常量, 内容与本string串相同. 
sscanf : https://blog.csdn.net/vitalia/article/details/52474761

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

struct node{
    int Complex,Flag;
    char var;
};

int main(){
    int t,n;
    cin>>t;

    while(t--){
        int cmp,cur_Com=0,max_Com=0,idx=1,Flag=0;
        bool vis[30];
        memset(vis,0,sizeof(vis));
        stack <node> st;
        string s,c1,c2,c3,c4;
        cin>>n>>s;
        if(s[2]=='1') cmp=0;
        else sscanf(s.c_str(),"O(n^%d)",&cmp);
        for(int i=1;i<=n;i++){
            cin>>c1;

            if(c1[0]=='F'){
                cin>>c2>>c3>>c4;
                if(!idx) continue;
                if(vis[c2[0]-'a']){idx=0;continue;}
                vis[c2[0]-'a']=1;
                st.push((node){cur_Com,Flag,c2[0]});
                if(Flag) Flag=1;
                else if(c3[0]=='n'&&c4[0]!='n') Flag=1;
                else if(c3[0]!='n'&&c4[0]!='n'){
                    int cc3=atoi(c3.c_str());
                    int cc4=atoi(c4.c_str());
                    if(cc3>cc4) Flag=1;
                }
                else if(c3[0]!='n'&&c4[0]=='n'){
                    cur_Com++;
                    max_Com=max(max_Com,cur_Com);
                }
            }

            else if(c1[0]=='E'){
                if(!idx) continue;
                if(st.empty()) {idx=0;continue;}
                node tmp=st.top();st.pop();
                cur_Com=tmp.Complex;
                vis[tmp.var-'a']=0;
                Flag=tmp.Flag;
            }

        }
        if(!idx||!st.empty()) cout<<"ERR"<<endl;
        else{
            if(max_Com==cmp) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

P3960 列队

题目描述

Sylvia 是一个热爱学习的女♂孩子。

前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。

Sylvia 所在的方阵中有

为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中的学生从 1 到

然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天中，一共发生了

在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达这样的两条指令：

向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条指令之后，空位在第
向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条指令之后，空位在第

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后，下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第

因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学的编号是多少。

注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后方阵中同学的编号可能是乱序的。

输入输出格式

输入格式：

输入共

第 1 行包含 3 个用空格分隔的正整数

接下来

输出格式：

按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学生的编号。

输入输出样例

输入样例#1：复制

输出样例#1：复制

1
1
4

说明

【输入输出样例 1 说明】

列队的过程如上图所示，每一行描述了一个事件。在第一个事件中，编号为

【数据规模与约定】

数据保证每一个事件满足

题解：https://www.luogu.org/blog/ztzshiwo001219/solution-p3960

#include <bits/stdc++.h>

using namespace std;
const int inf = 1000000008, maxn = 300005;
int w;

#define ll long long
vector <ll> a[maxn];
void read(int &x){
    int f=1;x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
struct Node {
    int v;
    Node *ls, *rs;
    void up(){
        v = ls->v + rs->v;
    }
}pool[maxn*50], *tail = pool, * root[maxn], *zero;
void build(){
    zero = ++tail;
    zero->ls = zero->rs = zero;
    zero->v = 0;
}
Node * newnode(){
    Node *nd = ++tail;//要有++tail
    nd->v = 0;
    nd->ls = nd->rs = zero;
    return nd;
}

int query(Node *nd, int pos, int lf = 1, int rg = w){
    if(lf == rg)return lf;
    if(nd == zero)nd = newnode();
    if(nd->ls == zero)nd->ls = newnode();
    if(nd->rs == zero)nd->rs = newnode();

    int mid = (lf + rg) >> 1;
    int t = mid - lf + 1 - nd->ls->v;
    if(pos <= t)return query(nd->ls, pos, lf, mid);
    else return query(nd->rs, pos-t, mid+1, rg);
}
void modify(Node *nd, int pos, int lf = 1, int rg = w){
    if(nd == zero)nd = newnode();
    if(lf == rg){nd->v = 1;return;}
    if(nd->ls == zero)nd->ls = newnode();
    if(nd->rs == zero)nd->rs = newnode();

    int mid = (lf + rg) >> 1;
    if(pos <= mid)modify(nd->ls, pos, lf, mid);
    else modify(nd->rs, pos, mid+1, rg);
    nd->up();
}
int main()
{
    //freopen("phalanx.in","r",stdin);
    //freopen("phalanx.out","w",stdout);
    int n, m, q;
    scanf("%d%d%d",&n, &m, &q);
    w = max(n, m) + q + 1;
    build();
    for(int i = 1; i <= n+1; i++)root[i] = newnode();
    while(q--){
        int x, y, z; ll ans;
        read(x), read(y);
        if(y != m){
            z = query(root[x], y);
            if(z < m)ans = 1ll* (x - 1) * m + z;
            else ans = a[x][z - m];
            printf("%lld
",ans);
            modify(root[x], z);
            a[n + 1].push_back(ans);

            z = query(root[n + 1], x); //id[x][y] have been deleted
            //printf("%lld %d
",ans, z);
            if(z <= n)ans =1ll* m * z;
            else ans = a[n + 1][z - n - 1];
            a[x].push_back(ans);
            modify(root[n + 1], z);
           // printf("%lld %d
",ans, z);
        }
        if(y == m){
            int z = query(root[n + 1], x);
            if(z <= n)ans =1ll* m * z;
            else ans = a[n + 1][z - n - 1];
            printf("%lld
",ans);
            modify(root[n + 1], z);
            a[n + 1].push_back(ans);
          //  printf("%lld %d
",ans, z);
        }

    }
    return 0;
}

View Code