2015 년 CM / ICPC 아시아 구장 봄 역 부분 해제
41576 단어 ACM장춘 역아시아 지역 경기Partial-Tr
F。Almost Sorted Array
한 배열 의 수가 거의 정렬 된 것 인지 아 닌 지 를 판단 한다. 거의 정렬 된 것 은 하 나 를 제거 한 후에 정렬 된 배열 이 될 수 있다 는 뜻 이다. 최 장 단일 증가 또는 단일 감소 서브 서열 만 구하 면 된다. 만약 에 길이 가 배열 의 길이 와 같 거나 배열 의 길이 - 1 과 같 으 면 일치 하 는 서열 이다.
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define For(a,l,r) for(int a=l;a<r;a++)
#define F first
#define S second
using namespace std;
typedef long long LL;
const LL mod = 9973;
const LL inf=0x3f3f3f3f;
const double pi=acos(-1);
const int N=200005;//
const int M=13;//
int T,n,m;
int a[100005];
int dp[100005];
int main()
{
#ifdef LOCALHEI
freopen("date.in","r",stdin);
freopen("date.out","w",stdout);
#endif
scanf("%d",&T);
while(T--)
//while(scanf("%d%d",&n,&m)!=EOF)
{
scanf("%d",&n);
int len=0;
scanf("%d",&a[0]);
dp[++len]=a[0];
for(int i=1;i<n;i++)
{
scanf("%d",&a[i]);
if(dp[len]<=a[i])dp[++len]=a[i];
else
{
int l=1,r=len;
while(l<=r)
{
int mid=(l+r)/2;
if(dp[mid]>a[i])r=mid-1;
else l=mid+1;
}
dp[l]=a[i];
}
}
//cout<<len<<endl;
if(len>=n-1)
{
puts("YES");
continue;
}
len=0;
dp[++len]=a[0];
for(int i=1;i<n;i++)
{
if(dp[len]>=a[i])dp[++len]=a[i];
else
{
int l=1,r=len;
while(l<=r)
{
int mid=(l+r)/2;
if(dp[mid]<a[i])r=mid-1;
else l=mid+1;
}
dp[l]=a[i];
}
}
//cout<<len<<endl;
if(len>=n-1)
{
puts("YES");
continue;
}
puts("NO");
}
return 0;
}
G。Dancing Stars on Me
이러한 점 을 모두 사용 하 는 상황 에서 정 다각형 을 구성 할 수 있 는 지, 변 의 길 이 는 정수 로 정 사각형 만 구성 할 수 있 는 지 를 판단 하 는 점 을 제시 합 니 다.정렬 은 각 대응 변 을 선택 하여 길이 가 같은 지 판단 하면 됩 니 다.
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define For(a,l,r) for(int a=l;a<r;a++)
#define F first
#define S second
using namespace std;
typedef long long LL;
const LL mod = 9973;
const LL inf=0x3f3f3f3f;
const double pi=acos(-1);
const int N=200005;//
const int M=13;//
struct node
{
int x,y;
}p[106];
bool cmp(node a,node b)
{
if(a.x==b.x)
return a.y<b.y;
else return a.x<b.x;
}
int T,n,m;
bool check()
{
sort(p,p+4,cmp);
long long s[5];
s[0]=(p[0].x-p[1].x)*(p[0].x-p[1].x)+(p[0].y-p[1].y)*(p[0].y-p[1].y);
s[1]=(p[0].x-p[2].x)*(p[0].x-p[2].x)+(p[0].y-p[2].y)*(p[0].y-p[2].y);
s[2]=(p[3].x-p[1].x)*(p[3].x-p[1].x)+(p[3].y-p[1].y)*(p[3].y-p[1].y);
s[3]=(p[2].x-p[3].x)*(p[2].x-p[3].x)+(p[2].y-p[3].y)*(p[2].y-p[3].y);
sort(s,s+4);
if(s[0]==s[3])
return true;
else
return false ;
}
int main()
{
#ifdef LOCALHEI
freopen("date.in","r",stdin);
freopen("date.out","w",stdout);
#endif
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
if(n!=4)
{
puts("NO");
continue;
}
if(check())
{
puts("YES");
}
else puts("NO");
}
return 0;
}
H - Partial Tree n 개 점 에서 한 그루 의 나 무 를 생 성 합 니 다. 각 노드 의 도수 가 다 르 고 가중치 도 다 르 기 때문에 최대 가중치 의 나 무 를 구 합 니 다.각 노드 는 적어도 한 도 는 있어 야 한다. 모두 2 * n - 2 도 이 고 나머지 n - 2 도 를 n 개 노드 에 나 누 어야 한다.문 제 는 무 게 를 각각 1 - > n - 2 로 바 꾸 고 가 치 는 각각 v [i] (2 < = i < = n - 1) 의 아 이 템 을 부피 가 n - 2 인 가방 에 넣 고 v [i] = f [i] - f [1] 로 바 꾸 었 다. 즉, 일부 도 를 1 로 바 꾸 는 노드 를 통 해 이 를 i 로 만 드 는 것 이다.완전 가방 으로 구 해 볼 수 있 습 니 다. 주의해 야 할 것 은 부피 가 x 인 아 이 템 을 넣 어 부 피 를 y 에 이 르 게 하 는 것 입 니 다. 그러면 이전에 넣 은 아 이 템 은 반드시 y - x 에 이 를 수 있어 야 합 니 다.
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define For(a,l,r) for(int a=l;a<r;a++)
#define F first
#define S second
using namespace std;
typedef long long LL;
const LL mod = 9973;
const LL inf=0x3f3f3f3f;
const double pi=acos(-1);
const int N=200005;//
const int M=13;//
int T,n,m;
int f[2016];
int dp[2016];
int main()
{
#ifdef LOCALHEI
freopen("date.in","r",stdin);
freopen("date.out","w",stdout);
#endif
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<n;i++)
scanf("%d",&f[i]);
for(int i=0;i<=n;i++)
dp[i]=-inf;
dp[0]=0;
for(int i=2;i<=n-1;i++)
for(int j=(i-1);j<=n-2;j++)
if(dp[j-(i-1)]!=-inf)
dp[j]=max(dp[j-(i-1)]+f[i]-f[1],dp[j]);
printf("%d
",f[1]*n+dp[n-2]);
}
return 0;
}
J - Chip Factory
몇 개의 수 를 주 고 이 숫자 중에서 서로 다른 세 개의 수 를 선택 하 십시오. a, b, c 는 가장 큰 (a + b) XORc 를 구 합 니 다.폭력 은 시간 을 초과 할 수 있 습 니 다. 사전 트 리 로 최적화 할 수 있 습 니 다. 먼저 이 수 를 사전 트 리 에 저장 한 다음 에 두 가지 구 와 판단 을 해 야 합 니 다. 주의해 야 할 것 은 abc 가 다 르 기 때문에 a + b 는 사전 트 리 에서 값 을 찾 을 때 판단 해 야 합 니 다.두 가지 방법: 하 나 는 bool 배열 을 직접 열 어 판단 하고 하 나 는 값 을 찾기 전에 a, b 를 트 리 에서 삭제 합 니 다.둘 다 붙 여 주세요.
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define For(a,l,r) for(int a=l;a<r;a++)
#define F first
#define S second
using namespace std;
typedef long long LL;
const LL mod = 9973;
const LL inf=0x3f3f3f3f;
const double pi=acos(-1);
const int N=200005;//
const int M=13;//
int T,n,m;
int a[1005];
struct node
{
bool fla[1000];
struct node *nextt[2];
int num;
};
struct node *root;
struct node *newset()
{
struct node *p;
p=new(node);
for(int i=0;i<2;i++)
{
p->nextt[i]=NULL;
}
p->num=0;
memset(p->fla,false,sizeof(p->fla));
return p;
}
void insert(int an,int pla)
{
struct node *p;
p=root;
p->num++;
for(int i=30;i>=0;i--)
{
int tep=0;
if((an&(1<<i))!=0)
tep=1;
if(p->nextt[tep]==NULL)
{
p->nextt[tep]=newset();
}
p=p->nextt[tep];
p->fla[pla]=1;
p->num++;
}
}
int que(int an,int x,int y)
{
node *p;
p=root;
int res=an;
for(int i=30;i>=0;i--)
{
//printf("%d===
",p->num);
int tep=0;
if((an&(1<<i))!=0)
tep=1;
if((p->nextt[tep^1]!=NULL)&&(((p->nextt[tep^1]->fla[x])&&(p->nextt[tep^1]->fla[y])&&(p->nextt[tep^1]->num>2))||((p->nextt[tep^1]->fla[x]==0)&&(p->nextt[tep^1]->fla[y])&&(p->nextt[tep^1]->num>1))||((p->nextt[tep^1]->fla[x])&&(p->nextt[tep^1]->fla[y]==0)&&(p->nextt[tep^1]->num>1))||((p->nextt[tep^1]->fla[x]==0)&&(p->nextt[tep^1]->fla[y]==0)&&(p->nextt[tep^1]->num>0))))
{
res|=(1<<i);
p=p->nextt[tep^1];
}
else if(p->nextt[tep]!=NULL)
{
res&=(~(1<<i));
p=p->nextt[tep];
// printf("i= %d %d==
",i,res);
}
}
return res;
}
void clearr(node * root)//
{
for(int i=0;i<2;i++)
{
if(root->nextt[i]!=NULL)
{
clearr(root->nextt[i]);
}
}
free(root);
}
int main()
{
#ifdef LOCALHEI
freopen("date.in","r",stdin);
freopen("date.out","w",stdout);
#endif
scanf("%d",&T);
while(T--)
{
root=newset();
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
insert(a[i],i);
}
// printf("%d=====
",root->num);
int ans=0;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
//printf("%d %d 9999
",a[i],a[j]);
int aaa=que(a[i]+a[j],i,j);
//cout<<que(a[i]+a[j],i,j)<<endl;
ans=max(ans,aaa);
}
printf("%d
",ans);
clearr(root);
}
return 0;
}
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define For(a,l,r) for(int a=l;a<r;a++)
#define F first
#define S second
using namespace std;
typedef long long LL;
const LL mod = 9973;
const LL inf=0x3f3f3f3f;
const double pi=acos(-1);
const int N=200005;//
const int M=13;//
int T,n,m;
int a[1005];
struct node
{
struct node *nextt[2];
int num;
};
struct node *root;
struct node *newset()
{
struct node *p;
p=new(node);
for(int i=0;i<2;i++)
{
p->nextt[i]=NULL;
}
p->num=0;
return p;
}
void insert(int an)
{
struct node *p;
p=root;
p->num++;
for(int i=30;i>=0;i--)
{
int tep=0;
if((an&(1<<i))!=0)
tep=1;
if(p->nextt[tep]==NULL)
{
p->nextt[tep]=newset();
}
p=p->nextt[tep];
p->num++;
}
}
void del(int an)
{
struct node *p;
p=root;
p->num--;
for(int i=30;i>=0;i--)
{
int tep=0;
if((an&(1<<i))!=0)
tep=1;
p=p->nextt[tep];
p->num--;
}
}
int que(int an)
{
node *p;
p=root;
int res=an;
for(int i=30;i>=0;i--)
{
int tep=0;
if((an&(1<<i))!=0)
tep=1;
if(p->nextt[tep^1]!=NULL&&p->nextt[tep^1]->num>0)
{
res|=(1<<i);
p=p->nextt[tep^1];
}
else if(p->nextt[tep]!=NULL)
{
res&=(~(1<<i));
p=p->nextt[tep];
}
}
return res;
}
void clearr(node * root)//
{
for(int i=0;i<2;i++)
{
if(root->nextt[i]!=NULL)
{
clearr(root->nextt[i]);
}
}
free(root);
}
int main()
{
#ifdef LOCALHEI
freopen("date.in","r",stdin);
freopen("date.out","w",stdout);
#endif
scanf("%d",&T);
while(T--)
{
root=newset();
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
insert(a[i]);
}
int ans=0;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
del(a[i]);
del(a[j]);
int aaa=que(a[i]+a[j]);
insert(a[i]);
insert(a[j]);
ans=max(ans,aaa);
}
printf("%d
",ans);
clearr(root);
}
return 0;
}
L - House Building 은 물체 의 표면적 을 구한다.정 면적 과 사방 높이 의 차 이 는 바로 돌출 된 표면적 이 므 로 한 번 옮 겨 다 니 면 된다.
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define For(a,l,r) for(int a=l;a<r;a++)
#define F first
#define S second
using namespace std;
typedef long long LL;
const LL mod = 9973;
const LL inf=0x3f3f3f3f;
const double pi=acos(-1);
const int N=200005;//
const int M=13;//
int T,n,m;
int a[55][55];
int main()
{
#ifdef LOCALHEI
freopen("date.in","r",stdin);
freopen("date.out","w",stdout);
#endif
scanf("%d",&T);
while(T--)
//while(scanf("%d%d",&n,&m)!=EOF)
{
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
long long ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(a[i][j]==0)
continue;
ans+=1;
if(a[i][j]>a[i-1][j])
ans+=(a[i][j]-a[i-1][j]);
if(a[i][j]>a[i][j-1])
ans+=(a[i][j]-a[i][j-1]);
if(a[i][j]>a[i+1][j])
ans+=(a[i][j]-a[i+1][j]);
if(a[i][j]>a[i][j+1])
ans+=(a[i][j]-a[i][j+1]);
}
printf("%lld
",ans);
}
return 0;
}
다른 것 은 내 가 충분히 강해 지면 다시 이야기 하 자 = orz
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 1233 절 대 컴퓨터 대학원 재시험모 성에 서 마을 의 교통 상황 을 조사 하여 얻 은 통계표 에는 임의의 두 마을 간 의 거리 가 열거 되 어 있다.성 정부의 '원활 한 공사' 목 표 는 성 전체의 어느 두 마을 간 에 도 도로 교통 을 실현 할 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.