Andrew Stankevich’s Contest #9解题报告 » ZOJ2702

ZOJ2702
ZOJ2702.cpp


#include <map>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 4096;

int main() {
	int n;
	int a[MAXN], c[MAXN], v;

	while (scanf("%d", &n) != EOF) {
		map<int, int> mp;
		for (int i = 0; i < n; ++i) {
			scanf("%d", &v);
			a[i] = -1;
			if (mp.count(v) > 0) {
				a[mp[v]] = i;
				c[i] = mp[v];
			} else {
				c[i] = -1;
			}
			mp[v] = i;
		}

		vector<int> ans;
		for (int i = 0; i < n; ) {
			int j = i + 1;
			while (j < n && c[j] == -1) {
				++j;
			}
			if (j == n) {
				break;
			} else if (a[j] != -1) {
				c[a[j]] = -1;
			}

			int k = j + 1;
			while (k < n && c[k] == -1) {
				++k;
			}
			if (k == n) {
				break;
			} else if (a[k] != -1) {
				c[a[k]] = -1;
			}

			ans.push_back(c[j]);
			ans.push_back(j);
			ans.push_back(c[k]);
			ans.push_back(k);

			for (; i <= k; ++i) {
				if (a[i] != -1) {
					c[a[i]] = -1;
				}
			}
		}

		sort(ans.begin(), ans.end());
		printf("%d\n", (int)ans.size() / 4);
		for (int i = 0; i < (int)ans.size(); i += 4) {
			printf("%d %d %d %d\n", ans[i] + 1, ans[i + 1] + 1, ans[i + 2] + 1, ans[i + 3] + 1);
		}
		puts("");
	}

	return 0;
}

/*
        Submit                  Problem          Run  Run
Run ID  Time       Judge Status ID      Language Time Memory User Name
                                                 (ms) (KB)
2116497 2010-03-18 Accepted     2702    C++      50   176    watashi@Zodiac
        17:01:16
*/

// O(n) is possible
5 Responses to “ZOJ2702”
  1. mao says:

    我的做法是,找出前i句中满足“AABB”、“ABAB”、“BABA”、“AAAA”情况之一的小节,记录位置。
    然后由i+1处继续往后寻找,但一直wa,不知为何?

    • watashi says:

      BABA => ABBA ?

      • mao says:

        写错。。
        简化一下,就是满足2A、2B 或者 4A这两种模式之一即可。
        我的思路是用一个数组poem存储诗歌;
        一个数组ct来做计数器,ct[i]存储在满足一个模式之前的第i句的出现次数;
        当有ct[i]=2、ct[j]=2或者ct[i]=4时,记录位置,总计数+1
        然后从模式之后的句子往后查找

        可行不?

        • watashi says:

          应该是对的吧,实现错了?

          • mao says:

            题上的例子得到的答案是一样滴。难道有什么边界?
            int poem[4001];
            byte ct[4001],res[4001];
            char buf[16];
            int main()
            {
            int n,index=0,i,j,k,l,counter,ans,trd;
            // FILE* file=freopen(“in.txt”,”r”,stdin);
            while(scanf(“%d”,&n)!=EOF)
            {
            for(i=1;i<=n;i++)
            scanf("%d",&poem[i]);
            memset(ct,1,sizeof(ct));
            memset(res,0,sizeof(res));
            k=0;
            counter=0;
            ans=0;
            trd=0;
            k=0;
            l=1;
            for(i=2;i<=n;i++)
            for(j=l;j<i;j++)
            {
            if(poem[j]==poem[i])
            {
            ct[j]++;
            if(ct[j]==3)
            trd=i;
            if(ct[j]%2==0)
            {
            counter++;
            if(ct[j]==2)
            {
            res[k++]=j;
            res[k++]=i;
            }
            if(ct[j]==4)
            {
            res[k++]=trd;
            res[k++]=i;
            }
            }
            if(counter==2)
            {
            ans++;
            counter=0;
            l=i+1;
            }
            break;
            }
            }
            printf("%d\n",ans);
            for(i=0;i<ans;i++)
            {
            for(j=0;j<4;j++)
            for(k=j;kres[i*4+k])
            {
            l=res[i*4+j];
            res[i*4+j]=res[i*4+k];
            res[i*4+k]=l;
            }
            printf(“%d %d %d %d\n”,res[i*4],res[i*4+1],res[i*4+2],res[i*4+3]);
            }
            puts(“”);
            }
            return 0;
            }

  2.  
Leave a Reply