首页 > ACM题库 > HDU-杭电 > HDU 2774-HOJ-Shuffle[解题报告]C++
2014
02-14

HDU 2774-HOJ-Shuffle[解题报告]C++

Shuffle

问题描述 :

You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle algorithm of your music player makes a random permutation of the songs in the playlist and plays the songs in that order until all songs have been played. Then it reshuffles and starts playing the list again.

You have a history of the songs that have been played. However, your record of the history of played songs is not complete, as you started recording songs at a certain point in time and a number of songs might already have been played. From this history, you want to know at how many different points in the future the next reshuffle might occur.

A potential future reshuffle position is valid if it divides the recorded history into intervals of length s (the number of songs in the playlist) with the first and last interval possibly containing less than s songs and no interval contains a specific song more than once.

输入:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

* One line with two integers s and n (1 ≤ s, n ≤ 100000): the number of different songs in the playlist and the number of songs in the recorded playlist history.
* One line with n space separated integers, x1, x2, …, xn (1 ≤ xi ≤ s): the recorded playlist history.

输出:

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

* One line with two integers s and n (1 ≤ s, n ≤ 100000): the number of different songs in the playlist and the number of songs in the recorded playlist history.
* One line with n space separated integers, x1, x2, …, xn (1 ≤ xi ≤ s): the recorded playlist history.

样例输入:

4
4 10
3 4 4 1 3 2 1 2 3 4
6 6
6 5 4 3 2 1
3 5
3 3 1 1 1
7 3
5 7 3

样例输出:

1
6
0
7

#include<cstdio>
#include<cstring>
#include<map>
#include<set>

using namespace std;

map<int,int> cnt;
set<int> sames;
bool no[100005];
int Ts,s,n;
int a[100005];

int main() {
	//freopen("input.txt","r",stdin);
	scanf("%d",&Ts);
	while(Ts--) {
		memset(no,0,sizeof(no));
		cnt.clear(),sames.clear();
		scanf("%d%d",&s,&n);
		for(int i=0;i<n;++i) scanf("%d",a+i);

		int idx=-1;
		for(int i=0;i<min(s,n);++i) {
			if(cnt[a[i]]>0) {idx=i; break;}
			cnt[a[i]]++;
		}
		if(idx==-1) {
			printf("%d\n",s); continue;
		}
		for(int i=idx;i<min(s,n);++i) {
			if(cnt[a[i]]>0) sames.insert(a[i]);
			cnt[a[i]]++;
		}
		for(int i=0;i<n;++i) {
			if(sames.size()) no[i]=1;
			if(i+s<n) {
				if(cnt[a[i+s]]>0) sames.insert(a[i+s]);
				cnt[a[i+s]]++;
			}
			if(cnt[a[i]]==2) sames.erase(a[i]);
			cnt[a[i]]--;
		}
		int ans=0;
		for(int i=0;i<idx;++i) {
			bool can=1;
			for(int j=i+1;j<n;j+=s) can &= !no[j];
			ans += can;
		} printf("%d\n",ans);
	}
}

  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 3,求得所有的为的总和sum—->所有数的总和
    printf( "Not Possible" );—->printf("impossible");
    对吗?

  3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge