csp-201612

20161201（中间数）

代码1

现将数字从小到大排序得到values[]，然后用vector<int> minNum，vector<int> maxNum 来表示每个数的比它小的数目和比它大的数目。若知道了minNum[i]，那么minNum[i+1]是下面这么算的。

1
2
3
4
5
6
7
8
if(values[i] == values[i+1]){
    minNum[i+1] = minNum[i];
}else{
    int a = 0;
    for(int j=i;j>=0&&values[j]==values[i];j--)
        a++;
    minNum[i+1] = minNum[i] + a;
}

对于maxNum的计算也是类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> values;
vector<int> minNum,maxNum;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    values.resize(n);
    minNum.resize(n);
    maxNum.resize(n);
    for(int i=0;i<n;i++) cin>>values[i];

    sort(values.begin(),values.end());
    for(int i=0;i<n;i++){
        if(i==0){
            minNum[i] = 0;
            int a = 0;
            for(int j=i;j<n&&values[j]==values[i];j++){
                a++;
            }
            maxNum[i] = n-a;
        }else{
            if(values[i-1] == values[i]){
                minNum[i] = minNum[i-1];
                maxNum[i] = maxNum[i-1];
            }else{
                int a = 0;
                for(int j=i-1;j>=0&&values[j]==values[i-1];j--)
                    a++;
                minNum[i] = minNum[i-1] + a;
                a = 0;
                for(int j=i;j<n&&values[j]==values[i];j++){
                    a++;
                }
                maxNum[i] = maxNum[i-1]-a;
            }
        }
    }
    //output
    bool flag = false;
    for(int i=0;i<n;i++){
        if(minNum[i]==maxNum[i]){
            cout<<values[i]<<endl;
            flag = true;
            break;
        }
    }
    if(!flag) cout<<"-1"<<endl;
}

20161202（工资计算）

代码1

这题把不同税前工资分段的税后工资分段算出来就可以了，然后if else

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int lowerBound[8] = {0,3500,5000,8000,12500,38500,58500,83500};
int rate[8] = {-1,97,90,80,75,70,65,55};
vector<array<int,2>> scopes(8); //表示各个税后工资段
int T;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>T;

    for(int i=0;i<8;i++){
        if(i==0){
            scopes[i][0] = 0;
            scopes[i][1] = 3500;
        }else if(i<7){
            scopes[i][0] = scopes[i-1][1];
            scopes[i][1] = scopes[i][0] + rate[i]*(lowerBound[i+1]-lowerBound[i])/100;
        }else{
            scopes[i][0] = scopes[i-1][1];
            scopes[i][1] = -1;
        }
    }
    int S = 0;
    for(int i=0;i<8;i++){
        if(scopes[i][1]==-1 || T<=scopes[i][1]){
            if(i==0){
                S = T;
            }else{
                S = (T-scopes[i][0])*100/rate[i]+lowerBound[i];
            }
            break;
        }
    }
    //output
    cout<<S<<endl;
}

20161203（权限查询）

代码1

当记录角色有哪些权限时，使用unordered_map<string,unoredered_map<string,int>> roleToAuth，我们用unordered_map<string,set<string>> userToRole 来表示每个用户有哪些角色。

当查询的时候，我先查是否有这个用户，然后再查询是否有这个权限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

unordered_map<string,unordered_map<string,int>> roleToAuth;
unordered_map<string,set<string>> userToRole;
int p,r,u,q;

int main(){
    //freopen("D://input.txt","r",stdin);
    string auth;
    cin>>p;
    while(p--) cin>>auth;
    cin>>r;
    for(int i=0;i<r;i++){
        string role;
        int num;
        cin>>role>>num;
        while(num--){
            cin>>auth;
            int k = auth.find(':');
            if(k == string::npos){
                roleToAuth[role][auth] = -1;
            }else{
                int level = stoi(auth.substr(k+1));
                string authName = auth.substr(0,k);
                if(roleToAuth[role].find(authName) != roleToAuth[role].end()){
                    roleToAuth[role][authName] = max(roleToAuth[role][authName],level);
                }else{
                    roleToAuth[role][authName] = level;
                }
            }
        }
    }
    cin>>u;
    for(int i=0;i<u;i++){
        string user,role;
        int num;
        cin>>user>>num;
        while(num--){
            cin>>role;
            userToRole[user].insert(role);
        }
    }
    cin>>q;
    while(q--){
        string user,auth,authName;
        cin>>user>>auth; //error
        int level;
        int k = auth.find(':');
        if(k==string::npos){
            authName = auth;
            level = -1;
        }else{
            authName = auth.substr(0,k);
            level = stoi(auth.substr(k+1));
        }

        if(userToRole.find(user)==userToRole.end()){ //error: authName
            cout<<"false"<<endl;
        }else{
            set<string>& st = userToRole[user];
            set<string>::iterator it = st.begin(); //这个用户的所有角色
            bool flag = false; //是否查询到指定的权限
            int level2 = -1; //查询到的指定权限的等级
            for(;it!=st.end();it++){
                string role = (*it);
                unordered_map<string,unordered_map<string,int>>::iterator it2 = roleToAuth.find(role);
                if(it2!=roleToAuth.end()){
                    unordered_map<string,int>::iterator it3 = (*it2).second.find(authName);
                    if(it3 != (*it2).second.end()){
                        flag = true;
                        level2 = max(level2,(*it3).second);
                    }
                }
            }
            if(!flag){
                cout<<"false"<<endl;
            }else{
                if(level2!=-1 && level==-1){
                    cout<<level2<<endl;
                }else if(level2!=-1 && level!=-1){
                    if(level<=level2){
                        cout<<"true"<<endl;
                    }else{
                        cout<<"false"<<endl;
                    }
                }else if(level2==-1&&level==-1){
                    cout<<"true"<<endl;
                }else{
                    cout<<"false"<<endl;
                }
            }
        }
    }
}

注意28行，因为在输入每个角色的很多权限时，可能出现auth1:1 和 auth1:2这两个输入，这是要比较1和2中较大者作为auth1的等级，一开始没有考虑这点时90分，考虑了就100分。还有60行，我被user，auth，authName给弄晕了，本来应该根据user来查询的，我写成根据authName来查询，而且我还忘了输入cin了。

20161204（压缩编码）

代码1

假设输入有n个点，那么考虑范围就是[0, n*2-2]，下面是递推公式。

其中W(i,j) 表示$a_i$ 到 $a_j$ 范围内的频率相加之和。

所以可以利用动态规划的方法，先算使得j-i=0的，再算j-i=3的，一直到j-i=n*2-2的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005

int n;
int C[2*MAXN-1][2*MAXN-1];
int W[2*MAXN-1][2*MAXN-1];
int F[2*MAXN-1];

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;

    for(int i=0;i<n;i++){
        cin>>F[2*i];
    }
    for(int len=0;len<=n*2-2;len=len+2){
        if(len==0){
            for(int i=0;i+len<2*n-1;i=i+2){
                int j = i+len;
                W[i][j] = F[i];
                C[i][j] = 0;
            }
        }else{
            for(int i=0;i+len<2*n-1;i=i+2){
                int j = i+len;
                W[i][j] = W[i][i] + W[i+2][j];
                for(int k=i+1;k<j;k=k+2){
                    int temp = C[i][k-1]+C[k+1][j] + W[i][j];
                    if(k==i+1) C[i][j] = temp;
                    else C[i][j] = min(temp,C[i][j]);
                }
            }
        }
    }
    //output
    cout<<C[0][2*n-2]<<endl;
}

这道题告诉我一个很重要的事实：能不用vector就不用vector，直接中静态数组，这样就是20分的区别，因为这题用vector就恰好超时，丢掉了那20分。

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家