题解

40 条题解

  • 3
    @ 2015-02-08 18:09:39

    这道题关键在于找到规律:
    XXXX XXYY XYYX XYXY
    四种情况包含了全部的2对数字情况。
    问题转化为:给你一个数字串,求每两对相同的数字是一组,求一共有多少组数字(组与组之间元素不重叠)。
    #include<iostream>
    using namespace std;
    int a[4007];
    int size;
    int main(){
    freopen("in.txt", "r", stdin);
    cin >> size;
    int i;
    for (i = 0; i < size; i++){
    cin >> a[i];
    }
    int from = 0;
    int temp = 0;
    int ans = 0;
    int j;
    for (i = 0; i < size; i++){
    for (j = from; j < i; j++){
    if (a[i] == a[j]){
    temp++;
    a[i] = a[j] = -1;
    break;
    }
    }
    if (temp == 2){
    temp = 0; ans++; from = i;
    }
    }
    cout << ans << endl;
    return 0;
    }

    • @ 2015-02-08 18:15:59

      楼下我的方法其实也对,就是复杂一些但是更通用。
      当给定的串是 XXXY XYXX 这样的不规则形状时,楼下方法依旧适用。
      思路如下:
      for(i=0;i<size;i++){
      求以a[i]作为第一个符号的最短串。
      }
      以a[i]开头的串有多种情况,那就建立一个类似字典树或者是类似状态机一样的东西,直到形成一个串为止,这样做复杂度可能会很高。

    • @ 2015-02-08 18:18:13

      这说明对问题转化的越简单,实现起来越简单,转化可以起到4两拨千斤的作用。

  • 2
    @ 2017-08-19 13:27:32
    #include <cstdio>
    
    int main() {
        int n, a[10005], r = 0, c = 0, f = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
    #ifdef LOCAL
        puts("===");
    #endif
        for(int i = 0; i < n; i++) {
            for(int j = f; j < i; j++) {
                if(a[i] == a[j]) {
                    c++;
    #ifdef LOCAL
                    printf("a[%d] == a[%d]: %d\n", i, j, a[i]);
                    for(int o = 0; o < n; o++)
                        printf("%d ", a[o]);
                    printf("\n");
    #endif
                    a[i] = a[j] = 0;
                    break;
                }
            }
            if(c == 2)
                r++, c = 0, f = i;
        }
        printf("%d", r);
        return 0;
    }
    
  • 0
    @ 2020-11-19 20:47:25

    #include <bits/stdc++.h>
    using namespace std;
    int num[4001];//源数据
    int word[10001];//可能出现的整数
    int two=0,four=0;
    int main()
    {
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>num[i];
    int sum=0;
    for(int i=0;i<n;i++)
    {
    word[num[i]]++;
    if(word[num[i]]==2)two++;//某一个数出现两次
    if(word[num[i]]==4)four++;//或某一个出现了四次
    if(two==2)//有两个数出现两次
    {
    sum++;
    memset(word,0,sizeof(word));//前面的数和后面的没关系
    two=0;
    four=0;
    }
    else if(four)//或有一个数出现四次
    {
    sum++;
    memset(word,0,sizeof(word));//前面的数和后面的没关系
    two=0;
    four=0;
    }
    }
    cout<<sum<<endl;
    return 0;
    }

  • 0
    @ 2018-09-24 16:52:23

    大概就是骗分小方式,来自大佬

    #include<iostream>
    using namespace std;
    int from=0,sum=0,hh=0;
    int a[10001];
    int n,i,j;
    int main()
    {
    cin>>n;
    for(i=0;i<n;i++){cin>>a[i];}
    for(i=0;i<n;i++)
    {
    for(j=from;j<i;j++)

    if(a[i]==a[j])
    {
    hh++;
    a[i]=0;
    a[j]=0;
    break;
    }
    if(hh==2)
    {
    hh=0;
    sum++;
    from=i;
    }
    }
    cout<<sum;
    return 0;
    }

  • 0
    @ 2018-05-20 21:26:52

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int main()
    {
    int n;
    cin>>n;
    int a;
    int lia[10001]={0},sum=0,zan=0;
    for(int i=1;i<=n;i++)
    {
    cin>>a;
    lia[a]=lia[a]+1;
    if(lia[a]==2)
    zan=zan+1;
    if(zan==2)
    {
    sum=sum+1,zan=0,memset(lia,0,sizeof(lia));
    }
    if(lia[a]==4)
    {
    sum=sum+1,zan=0;
    memset(lia,0,sizeof(lia));
    }
    }
    cout<<sum;
    return 0;
    }
    每找到两个成对的或者四个一样的算一句。找到后前面的都归零

  • 0
    @ 2017-10-19 22:25:21

    #include <cstdio>

    int main() {
    int n, a[10005], r = 0, c = 0, f = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    scanf("%d", &a[i]);
    #ifdef LOCAL
    puts("===");
    #endif
    for(int i = 0; i < n; i++) {
    for(int j = f; j < i; j++) {
    if(a[i] == a[j]) {
    c++;
    #ifdef LOCAL
    printf("a[%d] == a[%d]: %d\n", i, j, a[i]);
    for(int o = 0; o < n; o++)
    printf("%d ", a[o]);
    printf("\n");
    #endif
    a[i] = a[j] = 0;
    break;
    }
    }
    if(c == 2)
    r++, c = 0, f = i;
    }
    printf("%d", r);
    return 0;
    }

  • 0
    @ 2017-10-19 22:24:57

    #include <cstdio>

    int main() {
    int n, a[10005], r = 0, c = 0, f = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    scanf("%d", &a[i]);
    #ifdef LOCAL
    puts("===");
    #endif
    for(int i = 0; i < n; i++) {
    for(int j = f; j < i; j++) {
    if(a[i] == a[j]) {
    c++;
    #ifdef LOCAL
    printf("a[%d] == a[%d]: %d\n", i, j, a[i]);
    for(int o = 0; o < n; o++)
    printf("%d ", a[o]);
    printf("\n");
    #endif
    a[i] = a[j] = 0;
    break;
    }
    }
    if(c == 2)
    r++, c = 0, f = i;
    }
    printf("%d", r);
    return 0;
    }

  • 0
    @ 2015-02-08 16:39:21

    对于我这样的水人,这样的题永远都不水。
    #include<iostream>
    #include<string.h>
    #include<math.h>
    using namespace std;

    int a[4007];
    int len[4007];//from i how long it takes to form a string
    int second[4007];
    int size;
    int ans;
    void xxyy(){
    int i,j;
    for (i = 0; i < size; i++){
    for (j = second[i] + 1; j < len[i]; j++){
    if (len[i]>second[j]){
    len[i] = second[j];
    }
    }
    }
    }
    void xyxyORxyyx(){
    int i, j;
    for (i = 0; i < size; i++){
    for (j = i + 1; j < len[i]; j++){
    if (a[i] == a[j])continue;
    if (second[j] < second[i]){
    if (len[i]>second[i])len[i] = second[i];
    }
    else if(second[j]>second[i]){
    if (len[i]>second[j])len[i] = second[j];
    }
    }
    }
    }
    void go(){
    int i=0;
    ans = 0;
    while (1){
    int mi = i;
    for (; i < len[mi]; i++){
    if (len[i] < len[mi])mi = i;
    }
    i = len[mi]+1;
    if (i<=size)ans++;
    if(i>=size)break;
    }
    }
    int main(){
    freopen("in.txt", "r", stdin);
    cin >> size;
    int i;
    for (i = 0; i < size; i++)cin >> a[i];
    memset(len, 0, sizeof(len));
    for (i = 0; i < size; i++)len[i] = size;
    int last[10001];
    memset(last, -1, sizeof(last));
    for (i = 0; i < size; i++)second[i] = size;
    for (i = 0; i < size; i++){
    if (last[a[i]] != -1){
    second[last[a[i]]] = i;
    }
    last[a[i]] = i;
    }
    xxyy();
    xyxyORxyyx();
    go();
    cout << ans << endl;
    return 0;
    }

  • 0
    @ 2014-08-05 17:28:35

    贪心。。。
    不能再水。
    program p1236;
    var n:longint;
    a:array[0..4010] of longint;
    h:array[0..10010] of longint;
    i,sum,sum1,p1:longint;
    //
    procedure make;
    var j:longint;
    begin
    for j:=p1+1 to i do dec(h[a[j]]);p1:=i;
    end;
    //
    begin
    read(n);
    for i:=1 to n do
    begin
    read(a[i]);inc(h[a[i]]);
    if h[a[i]]=2 then inc(sum1);
    if sum1=2 then
    begin
    make;inc(sum);sum1:=0;
    end;
    if h[a[i]]=4 then
    begin
    make;inc(sum);sum1:=0;
    end;
    end;
    write(sum);
    end.

  • 0
    @ 2009-10-17 12:35:46

    Accepted 有效得分:100 有效耗时:0ms

    贪心是正解,不一定要DP。

    但是各位注意楼下的有误导!只有下面两种是可行的:

    1.f[x]=4

    2.f[x]=2并且前面出现过一个数字f[i]=2!(这点可以用flag真值来表示)

  • 0
    @ 2009-10-15 19:41:39

    “按顺序选”,因此可以用贪心优化。

    还是多费点时间写正确的算法呀。

  • 0
    @ 2009-09-24 15:18:31

    hash:pre[i]记录第i个数字在前面出现的位置,剩下来的就很简单了。

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-08-31 11:09:48

    第190题纪念。。。淅沥糊涂就过了

    My Answer:

    [red]

    var n,i,j,total:longint;

    a:array[1..10000] of longint;

    h:boolean;

    begin

    readln(n);

    total:=0;

    fillchar(a,sizeof(a),0);

    h:=false;

    for i:= 1 to n do

    begin

    read(j);

    inc(a[j]);

    if a[j] = 2 then

    begin

    if h then

    begin

    h:=false;

    inc(total);

    fillchar(a,sizeof(a),0);

    end

    else

    h:=true;

    end;

    end;

    writeln(total);

    end.

    [/red]

  • 0
    @ 2009-08-04 19:51:51

    职业生涯第200题,上帝的爱好

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-08-03 14:46:07

    我觉得贪心是正解~看你怎么贪了

    ---|---|---|---|---|---|---|---|---|

    对于楼下的楼下,贪心结果是3

    结果是1的话,就是你贪心方法错了~

    ---|---|---|---|---|---|---|---|---|

    贪心也是有方法,要讲技巧地~~~

    PS:本人的第180题,庆祝~~~

  • 0
    @ 2009-07-22 21:16:38

    都怎么了,正解绝对是动态规划,预处理是n^2,动规是n^2,贪心能过是数据太弱了啊!

  • 0
    @ 2009-07-02 20:02:09

    贪心应该不正确吧?

    对于这个数据:

    16

    1 2 3 3 4 4 5 5 6 6 7 7 8 8 2 1

    贪心结果是1,但最优解为3....

    请教大牛.

  • 0
    @ 2009-06-14 16:45:27

    简单!搜一遍就ok。秒杀!

    ---|---|---|---|---|---|---|---|---|---|

    关键点:

    1和2有多少中排列方式呢?

    6种!

    刚好把题目要求的xxyy,yxyx,yxxy,当然再补充个xxxx就搞定

    然后就是线性的时间复杂度。完毕!

    ---|---|---|---|---|--

    不知道出题的人是怎么想的.....好水.....

    ---|---|---|---|---|---|---|---|--

    纯数学方法,排列组合

  • 0
    @ 2009-05-23 16:06:46

    神啊,俺语文不好,能不能把题目说清楚点啊!

  • 0
    @ 2009-05-09 03:11:07

    #include "stdio.h"

    int main()

    {

    int n,i,j,x,find,ans,a[4010]={0};

    scanf("%d",&n);

    find=0;ans=0;

    for(i=1;i

信息

ID
1236
难度
5
分类
贪心 点击显示
标签
递交数
1564
已通过
577
通过率
37%
被复制
6
上传者