// 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;
}
資訊工程 (4)
