광동공업대학 2016 교전 결승전 - 사이버전 D E F G 문제
복잡해 보이는데...실칙 수제;
종이에 그림을 그리다 보니 제목에 만족하지 않는 경우는 ##가 연결되어 있다.다른 상황에는 적어도 한 가지 경로가 있어 문제의 뜻을 만족시키는 두 갈래 나무를 만들 수 있다.하지만 아마 경기를 할 때 구덩이가 생길까봐...하지만 사실은 정말 이렇게 간단해요.
/* ***********************************************
Author :angon
************************************************ */
#include <stdio.h>
char s[maxn];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t;
scan(t);
while(t--)
{
scanf("%s",s);
int len=strlen(s);
int flag=1;
for(int i=0;i<len;i++)
{
if(s[i]=='#'&&s[i+1]=='#')
{
printf("no
");
flag=0;
break;
}
}
if(flag)
printf("yes
");
}
return 0;
}
G:저는 물문제예요.
토조: 제목은 빈칸이 없다고 소개하지만 실제로는 빈칸이 있다. 무단wa는 한 번!
/* ***********************************************
Author :angon
************************************************ */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
#define REPP(i,k,n) for(int i=k;i<=n;i++)
#define scan(d) scanf("%d",&d)
#define scann(n,m) scanf("%d%d",&n,&m)
#define LL long long
#define maxn 1005
#define mod 100000007
/*
inline int read()
{
int s=0;
char ch=getchar();
for(; ch<'0'||ch>'9'; ch=getchar());
for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';
return s;
}
inline void print(int x)
{
if(!x)return;
print(x/10);
putchar(x%10+'0');
}
*/
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
char s[3000];
int t;
scan(t);
getchar();
while(t--)
{
gets(s);
int len=strlen(s);
int c[30];
memset(c,0,sizeof(c));
for(int i=1;i<len;i+=3)
{
if(c[s[i]-97]==0)
c[s[i]-97]++;
}
int ans=0;
for(int i=0;i<=26;i++)
{
if(c[i])
ans++;
}
printf("%d
",ans);
}
return 0;
}
E블록 고인물
아주 좋은 사고문제로 어떤 알고리즘도 필요하지 않지만 실제로는 그렇게 생각하지 않는다.
일단 이 성질을 발견하면 매우 간단해진다. 가장 긴 기둥을 찾으면 물이 가득 찬 상황에서 이동한 후에 왼쪽의 수면은 비체감이고, 오른쪽은 비체감이다.
이 성질이 있으면 좌우에서 한 번씩 쓸면 된다.
/* ***********************************************
Author :angon
************************************************ */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
#define REPP(i,k,n) for(int i=k;i<=n;i++)
#define scan(d) scanf("%d",&d)
#define scann(n,m) scanf("%d%d",&n,&m)
#define mst(a,k) memset(a,k,sizeof(a));
#define LL long long
#define maxn 1000005
#define mod 100000007
/*
inline int read()
{
int s=0;
char ch=getchar();
for(; ch<'0'||ch>'9'; ch=getchar());
for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';
return s;
}
inline void print(int x)
{
if(!x)return;
print(x/10);
putchar(x%10+'0');
}
*/
int a[maxn];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,t;
scan(t);
while(t--)
{
scan(n);
int maxc=-1,idx;
REP(i,0,n)
{
scan(a[i]);
if(a[i]>maxc)
{
maxc=a[i];
idx=i;
}
}
LL sum=0;
int last=a[0];//last
REP(i,1,idx)
{
if(a[i]<=last)//
sum+=(last-a[i]);
else // last
last=a[i];
}
last=a[n-1];
for(int i=n-1;i>idx;i--)
{
if(a[i]<=last)
sum+=(last-a[i]);
else
last=a[i];
}
printf("%lld
",sum);
}
return 0;
}
F 난 좋은 사람 4
dfs 매거자 집합 허용;
용척: 매 배수의 개수를 빼고 다시 뺀 것을 더하기;이 목적을 달성하기 위해: 모든 서브집합, 서브집합 원소 개수 홀수의res-=1e9/lcm;
원소 개수가 짝수인res+=1e9/lcm;
가지치기:lcm>1e9직접return;
최적화: 1 무게를 빼고 2 만약에 a[i]%a[j]=0, a[i]를 제거한다.
왜 안 터져요?
n<=50, 자집 개수는 2^50-1이지만 a[i]<=1000;최적화 2이기 때문에 최대 50개의 직접적인 배수 관계가 없는 수이다. 그러면 상당 부분의 a[i]가 비교적 커질 것이다. 이렇게 하면 가지를 자를 때 쉽게 자를 수 있다.
/* ***********************************************
Author :angon
************************************************ */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
#define REPP(i,k,n) for(int i=k;i<=n;i++)
#define scan(d) scanf("%d",&d)
#define scann(n,m) scanf("%d%d",&n,&m)
#define mst(a,k) memset(a,k,sizeof(a));
#define LL long long
#define maxn 1005
#define N 1000000000
/*
inline int read()
{
int s=0;
char ch=getchar();
for(; ch<'0'||ch>'9'; ch=getchar());
for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';
return s;
}
inline void print(int x)
{
if(!x)return;
print(x/10);
putchar(x%10+'0');
}
*/
int cnt,a[55],vis[55];
LL ret;
LL gcd(LL a,LL b)
{
return a%b==0?b:gcd(b,a%b);
}
LL lcm(LL a,LL b)
{
return a/gcd(a,b)*b;
}
void dfs(int num,int f, LL tmp)
{
if(tmp > N ) return ;
if(num == cnt)
{
if(f&1) ret -= (N/tmp);
else ret += (N/tmp);
return ;
}
dfs(num+1,f,tmp);
dfs(num+1,f+1,lcm(a[num],tmp));
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t,n;
scan(t);
while(t--)
{
scan(n);
REP(i,0,n) scan(a[i]);
mst(vis,0);
sort(a,a+n);
for(int i=0;i<n;i++){
if(vis[i]) continue;
for(int j=i+1;j<n;j++){
if(a[j]%a[i]==0)
vis[j]=1;
}
}
cnt=0;
REP(i,0,n)
if(vis[i]==0)
a[cnt++]=a[i];
ret=0;
dfs(0,0,1LL);
printf("%lld
",ret);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.