The Himalayas http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5341
签到
#include<cstdio>
int main(){
int t,n,a[];
while(~scanf("%d",&t)){
while(t--){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
int ans=;
for(int i=;i<n;i++){
if(a[i]>a[i-]&&a[i]>a[i+]){
ans++;
}
}
printf("%d\n",ans);
}
}
return ;
}
Pretty Poem http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5350
string
#include<cstdio>
#include<cctype>
#include<iostream>
using namespace std;
char sin[],sout[];
string a1,a2,a3,b1,b2,b3,c;
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%s",sin);
int ls=;
for(int i=;sin[i];i++){
if(isalpha(sin[i])){
sout[ls++]=sin[i];
}
}
bool flag=false;
for(int la=;la<=ls;la++){
for(int lb=;lb<=ls;lb++){
if(la*+lb*==ls){///"ABABA"
a1=a2=a3=b1=b2="";
int s=;
for(int i=;i<la;i++){
a1+=sout[s+i];
}
s+=la;
for(int i=;i<lb;i++){
b1+=sout[s+i];
}
s+=lb;
for(int i=;i<la;i++){
a2+=sout[s+i];
}
s+=la;
for(int i=;i<lb;i++){
b2+=sout[s+i];
}
s+=lb;
for(int i=;i<la;i++){
a3+=sout[s+i];
}
s+=lb;
if(a1==a2&&a1==a3&&b1==b2&&a1!=b1){
flag=true;
break;
}
}
if(la*+lb*<ls){///"ABABCAB"
a1=a2=a3=b1=b2=b3=c="";
int s=;
for(int i=;i<la;i++){
a1+=sout[s+i];
}
s+=la;
for(int i=;i<lb;i++){
b1+=sout[s+i];
}
s+=lb;
for(int i=;i<la;i++){
a2+=sout[s+i];
}
s+=la;
for(int i=;i<lb;i++){
b2+=sout[s+i];
}
s+=lb;
int lc=ls-*la-*lb;
for(int i=;i<lc;i++){
c+=sout[s+i];
}
s+=lc;
for(int i=;i<la;i++){
a3+=sout[s+i];
}
s+=la;
for(int i=;i<lb;i++){
b3+=sout[s+i];
}
s+=lb;
if(a1==a2&&a1==a3&&b1==b2&&b1==b3&&a1!=b1&&a1!=c&&b1!=c){
flag=true;
break;
}
}
}
if(flag) break;
}
if(flag) puts("Yes");
else puts("No");
}
return ;
}
Untrusted Patrol http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5343
并查集
#include<cstdio>
#include<cstring>
#define mt(a,b) memset(a,b,sizeof(a))
const int M=;
struct G {
struct E {
int v,next;
} e[M<<];
int le,head[M];
void init() {
le=;
mt(head,-);
}
void add(int u,int v) {
e[le].v=v;
e[le].next=head[u];
head[u]=le++;
}
} g;
class UnionFindSet { ///并查集
int par[M];
public:
void init() {
mt(par,-);
}
int getroot(int x) {
int i=x,j=x,temp;
while(par[i]>=) i=par[i];
while(j!=i) {
temp=par[j];
par[j]=i;
j=temp;
}
return i;
}
bool unite(int x,int y) {
int p=getroot(x);
int q=getroot(y);
if(p==q)return false;
if(par[p]>par[q]) {
par[q]+=par[p];
par[p]=q;
} else {
par[p]+=par[q];
par[q]=p;
}
return true;
}
} F;
bool vis[M];
int need[M];
int main() {
int t,n,m,K,u,v,L;
scanf("%d",&t);
while(t--) {
scanf("%d%d%d",&n,&m,&K);
mt(vis,);
for(int i=; i<K; i++) {
scanf("%d",&u);
vis[u]=true;
}
g.init();
while(m--) {
scanf("%d%d",&u,&v);
g.add(u,v);
g.add(v,u);
}
scanf("%d",&L);
for(int i=; i<L; i++) {
scanf("%d",&need[i]);
}
bool ans=true;
if(L<K) {
ans=false;
}
if(ans) {
F.init();
vis[need[]]=false;
for(int u=; u<=n; u++) {
if(!vis[u]) {
for(int i=g.head[u]; ~i; i=g.e[i].next) {
int v=g.e[i].v;
if(!vis[v]) {
F.unite(u,v);
}
}
}
}
for(int x=; x<L; x++) {
int u=need[x];
vis[u]=false;
for(int i=g.head[u]; ~i; i=g.e[i].next) {
int v=g.e[i].v;
if(!vis[v]) {
F.unite(u,v);
}
}
if(F.getroot(need[x-])!=F.getroot(u)) {
ans=false;
break;
}
}
}
if(ans) {
int num=;
for(int i=; i<=n; i++) {
if(F.getroot(i)==i) num++;
if(num>) {
ans=false;
break;
}
}
}
if(ans) puts("Yes");
else puts("No");
}
return ;
}
end