标签归档：洛谷

洛谷 P1886 滑动窗口

发表评论

单调队列板子题。第一次新学，仍需继续努力练习。

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
/*

洛谷 P1886 滑动窗口 STL程序（各种优化都做的不大好，时间略长，但能AC）
“单调队列”数据结构 参考文档：
1、https://blog.csdn.net/a_bright_ch/article/details/77076228
2、https://blog.csdn.net/zhelong3205/article/details/77624699
3、https://blog.csdn.net/er111er/article/details/78344161
4、https://www.luogu.org/blog/hankeke/solution-p1886

建议真心想学的可以参考材料自己动手写一个。

*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
int n, k;
int arr[1000005];
deque<int> dq,pq;
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    //单调队列求最小
    for (int i = 1; i <= n; i++) {
        //维护队尾并插入
        while (!dq.empty() && dq.back() > arr[i]) { //求最大和最小的区别在第二个条件是大于号还是小于号
            dq.pop_back();
            pq.pop_back();
        }
        dq.push_back(arr[i]);
        pq.push_back(i);
        //剔除无效队首并获得最优解
        while (!pq.empty() && pq.back() - pq.front() >= k) {
            dq.pop_front();
            pq.pop_front();
        }
        if (i >= k)cout << dq.front() << " ";
    }
    cout << endl;
    dq.clear();
    pq.clear();
    //单调队列求最大
    for (int i = 1; i <= n; i++) {
        //维护队尾并插入
        while (!dq.empty() && dq.back() < arr[i]) { //求最大和最小的区别在第二个条件是大于号还是小于号
            dq.pop_back();
            pq.pop_back();
        }
        dq.push_back(arr[i]);
        pq.push_back(i);
        //剔除无效队首并获得最优解
        while (!pq.empty()&&pq.back() - pq.front() >= k) {
            dq.pop_front();
            pq.pop_front();
        }
        if (i >= k)cout << dq.front()<< " ";
    }
   
}

洛谷 P1739 表达式括号匹配

发表评论

有两个智障问题需要注意：
1、不要忘考虑 这种“))((”的情况。
2、还会有“(@)”的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    char c;
    int cnter = 0;
    while ((c = getchar())!='@') {
        if (c == '(')cnter++;
        if (c == ')')cnter--;
        if (cnter < 0) {
            cout << "NO";
            return 0;
        }
    }
    if (!cnter)cout << "YES";
    else cout << "NO";
}

洛谷 P1115 最大子段和

发表评论

严格注意语句顺序不能改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int A[200005];
int mmax = 0x80000000;
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> A[i];
    int curSum = 0;
    for (int i = 1; i <= n; i++) {
        curSum += A[i];
        mmax = max(mmax, curSum);
        if (curSum < 0)curSum = 0;
    }
    cout << mmax;
}

洛谷 P1147 连续自然数和

发表评论

需要用到等差数列的性质，再稍微减减枝就可以了。只要能想到这些，写出来没难度。
令 $a < b$ ，a为首项，b为末项，为等差数列，公差为1。 则有 $(a+b)*(b-a+1)/2=n$。 即 $(a+b)*(b-a+1)=2*n$。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int main() {
    long long n;
    cin >> n;
    for (long long a = 1; a <= n/2; a++) {
        for (long long b = a; b <= n/2+1; b++) {
            long long l = (a + b)*(b - a + 1);
            if (l == 2 * n)cout << a << " " << b << endl;
            if (l > 2 * n)break;
        }
    }
}

洛谷 字串变换

发表评论

题号：P1032
不是特好写，用了Map。除此之外他题里面有一点没说清楚，也就是替换字符串的时候每个字符串不同位置各替换一次，示例：
Original String:”baaba”
Map:”a”=>”b”
Generated String:{“bbaba”,”babba”,”baabb”}
就是这样。代码如下：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<functional>
using namespace std;
string A, B;
int n = 1;
string p[10][2];
queue<string> qs;
queue<int> qn;
map<string, bool> dic;
inline string replace(const string& origin, const string& toreplace, const string& replacement,int time) {
    string s = origin;
    int curpos = 0;
    time--;
    while (s.find(toreplace, curpos) != string::npos&&time) {
        curpos = s.find(toreplace, curpos)+toreplace.length();
        time--;
    }
    if (s.find(toreplace, curpos) != string::npos) {
        s.replace(s.find(toreplace, curpos), toreplace.length(), replacement);
        return s;
    }
    return "";
}
int main() {
    cin >> A >> B;
    while (cin >> p[n][0] >> p[n][1])n++;
    qs.push(A); qn.push(0);
    while (!qs.empty()) {
        string s = qs.front();
        int time = qn.front();
        qs.pop(); qn.pop();
        if (dic.count(s) || time > 10)continue;
        dic[s] = true;
        if (s == B) {
            cout << time;
            return 0;
        }
        for (int i = 1; i < n; i++) {
            string s2;
            for (int j = 1;; j++) {
                s2= replace(s, p[i][0], p[i][1],j);
                if (s2 == "")break;
                if (!dic.count(s2) && time + 1 <= 10) {
                    qs.push(s2); qn.push(time + 1);
                }
            }
        }
    }
    cout << "NO ANSWER!";
}

洛谷 加分二叉树

发表评论

题号：P1040
很有意义，想了不短时间，和一位群里的同学讨论了一下：代码如下：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
int n;
struct re{
    int i;
    string s;
    re(){
       
    }
    re(int i,string s){
        this->i=i;
        this->s=s;
    }
    re operator = (const re r){
        this->i=r.i;
        this->s=r.s;
        return *this;
    }
}f[32][32];
int scores[35];
string construction(int num){
    string s="";
    while(num!=0){
        s.insert(0,1,'0'+num%10);
        num/=10;
    }
    s+=' ';
    return s;
}
re dfs(int l,int r){
    if(l==r)return re(scores[l],construction(l));
    if(l>r)return re(1,"");
    if(f[l][r].i!=0)return f[l][r];
    int mm=0;
    string s;
    for(int i=l;i<=r;i++){
        re re1=dfs(l,i-1);
        re re2=dfs(i+1,r);
        if(mm<re1.i*re2.i+scores[i]){
            mm=re1.i*re2.i+scores[i];
            s=construction(i)+re1.s+re2.s;
        }
    }
    return f[l][r]=re(mm,s);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>scores[i];
    re re1=dfs(1,n);
    cout<<re1.i<<endl;
    cout<<re1.s;
}

洛谷 谁拿了最多奖学金

发表评论

这题本身没啥好说的，非常简单，要说的是C++的一个特性。
这个题写的比较复杂，其实不用这么多空间，也不要排序，直接线性处理就行了。但是我写题写习惯了，又接着搞排序，就出了这么个问题。

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
#include<bits/stdc++.h>
using namespace std;
int n;
struct stu{
    string name;
    int fs,cs;
    char sl,wp;
    int an;
    int money;
    stu(){
        money=0;
    }
    bool operator < (const stu& s2){
        return money>=s2.money;
    }
}stus[105];
int sum=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>stus[i].name>>stus[i].fs>>stus[i].cs>>stus[i].sl>>stus[i].wp>>stus[i].an;
    for(int i=1;i<=n;i++){
        if(stus[i].fs>80&&stus[i].an>=1)stus[i].money+=8000;
        if(stus[i].fs>85&&stus[i].cs>80)stus[i].money+=4000;
        if(stus[i].fs>90)stus[i].money+=2000;
        if(stus[i].fs>85&&stus[i].wp=='Y')stus[i].money+=1000;
        if(stus[i].cs>80&&stus[i].sl=='Y')stus[i].money+=850;
        sum+=stus[i].money;
    }
    sort(stus+1,stus+n+1);
    cout<<stus[1].name<<endl;
    cout<<stus[1].money<<endl;
    cout<<sum;
}

问题就出在比较的>=号上。查找了资料（地址http://blog.sina.com.cn/s/blog_532f6e8f01014c7y.html），我没细看，总结出来就是sort的cmp不能用带=号的。这个问题我最后就用stable_sort解决了。好用。代码如下：

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
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct stu{
    string name;
    int fs,cs;
    char sl,wp;
    int an;
    int money;
    bool operator < (const stu& s2) const{
        return money>s2.money;
    }
}stus[205];
int sum1=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>stus[i].name>>stus[i].fs>>stus[i].cs>>stus[i].sl>>stus[i].wp>>stus[i].an;
    }
    for(int i=1;i<=n;i++){
        if(stus[i].fs>80&&stus[i].an>=1)stus[i].money+=8000;
        if(stus[i].fs>85&&stus[i].cs>80)stus[i].money+=4000;
        if(stus[i].fs>90)stus[i].money+=2000;
        if(stus[i].fs>85&&stus[i].wp=='Y')stus[i].money+=1000;
        if(stus[i].cs>80&&stus[i].sl=='Y')stus[i].money+=850;
        sum1+=stus[i].money;
    }
    stable_sort(stus+1,stus+n+1);
    cout<<stus[1].name<<endl;
    cout<<stus[1].money<<endl;
    cout<<sum1;
}

NOIP2017 普及组第三道 棋盘

发表评论

这题写的异常难受……先想着用动态规划，难受死了，才20分。然后后来再看题解，用记忆化BFS，写的也难受，主要是太难想，终于AC了。开心~

写了有6、7个钟头吧。挺羞愧的。。。我写这种题怎么能这么长时间呢……

所有测试点全部0ms。

成就感极高。

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
#include<iostream>
#include<memory.h>
#include<queue>
using namespace std;
struct qs { //Convenient for passing parameters
    int tx, ty, os, rs, sc; //destination's coordinate (x,y) :tx,ty ;previous point::original status of color,real status of color :os,rs ;previous point's score:sc.
    qs(int tx1, int ty1, int os1, int rs1, int sc1) {
        tx = tx1; ty = ty1; os = os1; rs = rs1; sc = sc1;
    } //the init of struct
};
int m, n;
int arr[105][105], f[105][105]; //arr stores the color(status) of all coordinate; f stores the least gold the person will spend
int shiftx[4] = { 1,-1,0,0 }, shifty[4] = { 0,0,1,-1 }; //shifts for the coordinate
queue<qs> q;
void execute(qs o) {
    //Calculate New Score
    //Compare Which one is smaller
    //Only when the new one is smaller one,will the program insert the queue
    int nscore = 0x7fffffff;
    if (o.rs != -1 && arr[o.tx][o.ty] != -1) { // C2C(R2R/Y2Y/R2Y/Y2R) {"C"："Color","2":"To","R":"Red","Y":"Yellow"};
        if (o.rs == arr[o.tx][o.ty])nscore = o.sc; // R2R/Y2Y
        else nscore = o.sc + 1; // R2Y/T2R
        if (nscore < f[o.tx][o.ty] || o.tx==1&&o.ty==1) { //o.tx==1&&o.ty==1 is to create an entrance for the inital queue push
            f[o.tx][o.ty] = nscore;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], arr[o.tx][o.ty], arr[o.tx][o.ty], nscore));
        }
    }
    else if (o.os != -1 && arr[o.tx][o.ty] == -1) { // C2N
        if (o.os == 0 && o.sc + 2 < f[o.tx][o.ty]) { //Assume that the temporary color of current cell is Red
            f[o.tx][o.ty] = nscore = o.sc + 2;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 0, nscore));
            nscore += 1;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 1, nscore));
        }
        else if (o.os == 1 && o.sc + 2 < f[o.tx][o.ty]) { //Assume that the temporary color of current cell is Yellow
            f[o.tx][o.ty] = nscore = o.sc + 2;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 1, nscore));
            nscore += 1;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 0, nscore));
        }
    }
}
int main() {
    memset(arr, -1, sizeof(arr));
    memset(f, 0x7f, sizeof(f));
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        arr[x][y] = c;
    }
    f[1][1] = 0;
    q.push(qs(1, 1, arr[1][1], arr[1][1], 0));
    while (!q.empty()) {
        qs cur = q.front();
        q.pop();
        if (cur.tx > m || cur.ty > m || cur.tx < 1 || cur.ty < 1)continue;
        execute(cur);
    }
    cout << (f[m][m] == 0x7f7f7f7f ? -1 : f[m][m]) << endl;
}

洛谷 P1120 小木棍 ［数据加强版］

发表评论

写的很绝望……看了三遍所有题解仍然69……

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
#include<bits/stdc++.h>
using namespace std;
int n, sum = 0;
int lens[100] = { 0 };
bool visited[100] = { false };
int sums[100] = { 0 };
int o_min = 0, o_max;
vector<int> divisors;
int min_len;
inline bool dfs(int curpos, int curvalue, int groups){
    if (curvalue == min_len){
        if (groups == sum / min_len - 1)return true;
        else{
            int i;
            for (i = 1; i <= n; i++){
                if (!visited[i])break;
            }
            assert(i != n + 1);
            visited[i] = true;
            bool flag = dfs(i, lens[i], groups + 1);
            visited[i] = false;
            return flag;
        }
    }
    bool flag_finished = false;
    for (int i = curpos + 1; i <= n; i++){
        if (curvalue + lens[n] > min_len || curvalue + sums[i]<min_len)break;
        if (visited[i] || curvalue + lens[i] > min_len)continue;
        visited[i] = true;
        if (dfs(i, curvalue + lens[i], groups))flag_finished = true;
        visited[i] = false;
        if (flag_finished)return true;
        for (int j = i + 1; j <= n; j++){
            if (lens[j] != lens[i]){
                i = j - 1;
                break;
            }
        }
    }
    return false;
}
inline bool process(int min_length){
    min_len = min_length;
    visited[1] = true;
    bool flag = dfs(1, lens[1], 0);
    visited[1] = false;
    return flag;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> lens[i];
        if (lens[i] > 50){
            i--;
            n--;
        }
    }
    sort(lens + 1, lens + n + 1, greater<int>());
    for (int i = 1; i <= n; i++){
        o_min = max(o_min, lens[i]);
        sum += lens[i];
    }
    for (int i = n; i >= 1; i--){
        sums[i] = sums[i + 1] + lens[i];
    }
    o_max = sum;
    for (int i = o_min; i <= o_max / 2; i++){
        if (o_max%i == 0)divisors.push_back(i);
    }
    divisors.push_back(o_max);
    for (int i = 0; i < divisors.size(); i++){
        if (process(divisors[i])){
            cout << divisors[i];
            break;
        }
    }
}

20180811日更新：已经AC。
这题真的很麻烦，之前做过一回，69分放弃了，今天又重新做，改到了78AC22TLE，又看题解里的优化终于改到了AC。
题解：https://www.luogu.org/blog/complexity/solution-p1120
https://www.luogu.org/blog/cm-nanyi2018/solution-p1120
https://www.luogu.org/blog/ogawa/solution-p1120

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<functional>
using namespace std;
int n,lens[70],curLen,totSum=0;
int bucket[60],lst[60],lstPtr=0;
vector<int> possibleLen;
inline int check(){
    int i;
    for(i=1;i<=lstPtr;i++)if(bucket[lst[i]]!=0)return i;
    return i;
}
inline bool dfs(int lstPos,int len){//have already added lst[lstPos] before entering this recursive function
    if(len==totSum||len==totSum-curLen)return true;
    if(len%curLen==0){
        int i=check();
        bucket[lst[i]]--;
        bool flag=dfs(i,len+lst[i]);
        bucket[lst[i]]++;
        return flag;
    }
    int curRemain=curLen-len%curLen;
    for(int i=lstPos;i<=lstPtr;i++){
        if(lst[i]>curRemain||bucket[lst[i]]==0)continue;
        bucket[lst[i]]--;
        if(dfs(i,len+lst[i])){
            bucket[lst[i]]++;
            return true;
        }
        bucket[lst[i]]++;
        if(curRemain==lst[i])return false;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int maxV=0;
    for(int i=1;i<=n;i++){
        cin>>lens[i];
        if(lens[i]>50){
            i--;n--;
            continue;
        }
        bucket[lens[i]]++;
        maxV=max(maxV,lens[i]);
    }
    for(int i=50;i>=1;i--)if(bucket[i]!=0)lst[++lstPtr]=i;
    for(int i=1;i<=n;i++)totSum+=lens[i];
    for(int i=maxV;i<=totSum/2;i++)if(totSum%i==0)possibleLen.push_back(i);
    possibleLen.push_back(totSum);
    bucket[lst[1]]--;
    for(int i=0;i<possibleLen.size();i++){
        curLen=possibleLen[i];
        if(dfs(1,lst[1])){
            cout<<curLen;
            return 0;
        }
    }
}

[USACO1.2]命名那个数字 Name That Number

发表评论
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
#include<bits/stdc++.h>
using namespace std;
vector<string> Dict; //用Dict存放所有字典中的名字
string str; //给定的编号
const char * str_trans = "2223334445556667 77888999"; //使用该C-风格字符串来存放A-Z(除去Q和Z这24个字母所对应的数字)
int main(){
    ios::sync_with_stdio(false); //只用cin/cout加快IO速度
    cin >> str;
    string tmp;
    while (cin >> tmp){ //将后面所有的字符串循环读入到tmp中，再放到Vector尾，(cin>>tmp)即可以起到读入字符串的作用，也可以起到判断文件是否到达末尾。详情请阅读C++ Primer Plus。
        Dict.push_back(tmp);
    }
    int len = str.length();
    bool global_flag = false;
    for (int i = 0; i < Dict.size(); i++){ //遍历所有字典元素，因为字典元素少
        if (len != Dict[i].length())continue; //剪枝，如果字符串位数不一样就没有必要比较。
        bool flag = true;
        for (int j = 0; j < len; j++){
            if (str_trans[Dict[i][j] - 'A'] != str[j]){ //比对字典中每个字符对应的数字是否与输入的每个数字相同
                flag = false; //不相同直接跳出循环
                break;
            }
        }
        if (flag){ //相同则输出该单词
            cout << Dict[i] << endl;
            global_flag = true;
        }
    }
    if (!global_flag){ //如果没有一个单词符合要求，就输出NONE。
        cout << "NONE" << endl;
    }
}