// WA
// BY taichunmin
// NCPC 2011 pb
#include<iostream>
#include<fstream>
#include<sstream>
using namespace std;
int va[1000000];
int va_c;
int main()
{
	//freopen("pb.in","r",stdin);
	int ta;
	cin>>ta;
	string sa;
	while(ta--)
	{
		int ia,ib;
		cin>>ia;
		cin.get();
		getline(fin,sa);
		va_c=0;
		istringstream ssin(sa);
		while(ssin>>ib)
		{
			bool ba=true;
			for(int k=0;k<va_c;k++)
				if(va[k]>=ib)
				{
					va[k]=ib;
					ba=false;
					break;
				}
			if(ba)va[va_c++]=ib;
		}
		cout<<va_c<<endl;
	}
	return 0;
}

 

// WA
// BY taichunmin
// NCPC 2011 pd
#include<iostream>
#include<sstream>
#include<fstream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int ia,ib;
struct ta_t
{
	string n;
	int v;
}attr[10];
int fa(string sa)
{
	bool is_num=true;
	for(int i=0;i<sa.size() && is_num;i++)
		if(!('0'<=sa[i] && sa[i]<='9')is_num=false;
	if(is_num)
	{
		istringstream ssin(sa);
		int temp;
		ssin>>temp;
		return temp;
	}
	else
	{
		for(int i=0;i<ia;i++)
			if(attr[i].n==sa)return attr[i].v;
	}
	return 2147483647;
}
int main()
{
	//freopen("pd.in","r",stdin);
	int ta;
	cin>>ta;
	while(ta--)
	{
		cin>>ia>>ib;
		string sa,sname,sx,sy;
		for(int i=0;i<ia;i++)
			cin>>attr[i].n>>attr[i].v;
		cin.get();
		bool ba=true;
		for(int i=0;i<ib;i++)
		{
			getline(cin,sa);
			if(!ba)continue;
			istringstream ssin(sa);
			ssin>>sname;
			bool bb=true;
			while(getline(ssin,sa,'('))
			{
				ssin>>sx;
				getline(ssin,sy,')');
				sy.erase(0,3);
				//cout<<"sy = "<<sy<<endl;
				if(fa(sx)<=fa(sy))
				{
					bb=false;
					break;
				}
			}
			if(bb)
			{
				ba=false;
				cout<<sname<<endl;
			}
		}
	}
}

 

// AC
// BY morris1028
// NCPC 2011 ph
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
int A[100000],HASH[1000000],size;
struct Node{
	int v,s;
	int next;
}Node[200000];
int insHash(int v,int index)
{
	int m = v%1000000;
	if(HASH[m]==0) {
		size++;
		HASH[m]=size;
		Node[size].v=v, Node[size].s=index;
		Node[size].next=0;
		return -1;
	}
	int now=HSAH[m],pre=0;
	while(now)
	{
		if(Node[now].v>v || (Node[now].v==v && Node[now].s>index))
			break;
		else pre=now, now=Node[now].next;
	}
	size++;
	if(pre == 0) HASH[m]=size;
	else Node[pre].next=size;
	Node[size].v=v,Node[size].s=index;
	Node[size].next=now;
	return -1;
}
int find(int v,int index)
{
	int m=v%1000000;
	int now=HASH[m], pre=0;
	while(now)
	{
		if(Node[now].v==v && Node[now].s>index)
			return Node[now].s;
		else pre=now, now=Node[now].next;
	}
	return -1;
}
int Print(){
	int now, pre, i=0;
	for(int i=0;i<10;i++)
	{
		now=HASH[i];
		while(now)
		{
			printf("(%d,%d)->",Node[now].v,Node[now].s);
			pre=now, now=Node[now].next;
		}
		puts("===");
	}
	return 0;
}
int main(){
	//freopen("ph.in","r",stdin);
	int n,k,i;
	while(scanf("%d", &n)==1 && n) {
		for(i=0;i<n;i++)
			scanf("%d",&A[i];
		memset(HASH, 0, sizeof(HASH));
		scanf("%d", &k);
		int sum=0,tmp;
		size=1;
		for(i=0;i<n;i++)
		{
			A[i]%=k;
			sum+=A[i];
			sum%=k;
			if(sum<0) sum+=k;
			insHash(sum,i);
		}
		/* Print();*/
		sum=0;
		int flag=0;
		tmp=find(0,-1);
		if(tmp!=-1)
		{
			printf("%d %d\n",1,tmp+1);
			flag=1;
		}
		for(i=0;i<n;i++){
			A[i]%=k;
			sum+=A[i];
			sum%=k;
			if(sum<0) sum+=k;
			tmp=find(sum,i);
			/* printf("%d\n",tmp);*/
			if(tmp!=-1 && flag==0)
			{
				printf("%d %d\n",i+2,tmp+1);
				flag=1;
				break;
			}
		}
		if(flag==0)
			printf("no solutions.\n");
	}
	return 0;
}
/*
7
2 5 1 -4 5 9 3
10
11 -3 1 13 -5 6 1 -8 -4 5
10
*/

 

// AC
// BY morris1028
// NCPC 2011 pk
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define oo 2147483647
int map[1000][1000],Mt[1000];
int gcd(int x,int y)
{
	int t;
	while(y)
		t=x, x=y, y=t%y;
	return x;
}
int Used[1000], Time[1000], Ans;
int DFS(int T,int now,int start) {
	int last= oo,i,tmp,flag=0,ttry=0;
	Time[now] = T;
	/*printf("%d %d\n",now,T);*/
	for(i=0;i<Mt[now];i++){
		if(Used[map[now][i]]==0) {
			used[map[now][i]]=1;
			tmp=DFS(T+1, map[now][i],0);
			if(tmp>=T) flag=1;
			last=tmp<last?tmp:last;
			ttry++;
		} else {
			tmp=Time[map[now][i]];
			last=tmp<last?tmp:last;
		}
	}
	if(start==1) {
		if(ttry>1)
			Ans++;
	} else {
		Ans += flag;
	}
	/*printf("key : %d %d\nn", now,flag);*/
	return last;
}
int main() {
	//freopen("pk.in","r",stdin);
	int T,i,j,A[1001],n;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&A[i]);
		memset(map, 0, sizeof(map));
		memset(Mt, 0, sizeof(Mt));
		memset(Used, 0, sizeof(Used));
		memset(Time, 0, sizeof(Time));
		Ans=0;
		for(i=0;i<n;i++) {
			for(j=i+1;j<n;j++) {
				int tmp=gcd(A[i],A[j]);
				if(tmp!=1) {
					map[i][Mt[i]++]=j;
					map[j][Mt[j]++]=i;
				}
			}
		}
		for(i=0;i<n;i++)
			if(Used[i]==0) {
				Used[i] =1,Time[i] = 1;
				DFS(1,i,1);
			}
		printf("%d\n",Ans);
	}
	return 0;
}
創作者介紹

亂貼小站

和風信使 發表在 痞客邦 PIXNET 留言(0) 人氣()