BUPT 2014 신입생 여름방학 개인 순위 매치11
BOJ488 막내 동생 개수.
악의적인 문제
통분법으로 하고, 먼저 첫 번째 코드로 어떤 txt 파일에 표를 작성한 다음, 두 번째 코드의 그룹 부분으로 복사한다. (0 (1) 분통)#include <cstdio>
const long long MAX = 1000000100;
const long long N = 1000000000;
const long long BASE = 10000;
bool used[MAX];
int main(void)
{
freopen("out.txt","w",stdout);
int cnt = 0;
for(long long i = 2; i <= N; ++i){
if(!used[i]){
cnt++;
for(long long j = i *i; j <= N; j += i)
used[j] = true;
}
if(i % BASE == 0)
printf("%d,",cnt);
}
return 0;
}
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1;
char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
bool Prime(int x)
{
if (x == 1)
return false;
else if (x <= 0)
return false;
else if (x == 2)
return true;
else
{
for(ll i = 2; i*i <= x; i++)
if (x%i == 0)
return false;
return true;
}
}
const long long MAX = 1000000100;
const long long N = 1000000000;
const long long BASE = 10000;
int a[]= {};
int main()
{
int n;
// freopen("data.txt","r",stdin);
while(read(n))
{
int temp=n/BASE;
int ans;
if(temp==0)
ans=0;
else
ans=a[temp-1];
for(int i=BASE*temp; i<=n; i++)
if(Prime(i))
ans++;
printf("%d
",ans);
}
return 0;
}
본문
최대 반복 하위 문자열 길이 +1
모범 문제로 풀 수 있는데, 어쨌든 방법이 유난히 많죠.#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n) {
if(n < 0) {
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n) {
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------------------------------------------
const int MAXN=1000010;
void radix(int *str,int *a,int *b,int n,int m)
{
static int count[MAXN];
memset(count,0,sizeof(count));
for(int i=0;i<n;++i)
++count[str[a[i]]];
for(int i=1;i<=m;++i)
count[i]+=count[i-1];
for(int i=n-1;i>=0;--i)
b[--count[str[a[i]]]]=a[i];
}
void suffix_array(int *str,int *sa,int n,int m)
{
static int rank[MAXN],a[MAXN],b[MAXN];
for(int i=0;i<n;i++)
rank[i]=i;
radix(str,rank,sa,n,m);
rank[sa[0]]=0;
for(int i=1;i<n;i++)
rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
for(int i=0;1<<i <n;++i)
{
for(int j=0;j<n;++j)
{
a[j]=rank[j]+1;
b[j]=j +(1<<i)>=n? 0:rank[j+(1<<i)] +1;
sa[j]=j;
}
radix(b,sa,rank,n,n);
radix(a,rank,sa,n,n);
rank[sa[0]]=0;
for(int j=1;j<n;j++)
{
rank[sa[j]]=rank[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]);
}
}
}
string duplicate_substr(string str)
{
string rev;
static int s[MAXN],sa[MAXN],rank[MAXN],h[MAXN];
int n=str.length();
copy(str.begin(),str.end(),s);
suffix_array(s,sa,n,256);
for(int i=0;i<n;++i)
rank[sa[i]]=i;
int k=0;
int ans1=0,pos1=0;
for(int i=0;i<n;i++)
{
k= k==0? 0:k-1;
while(rank[i]>0&&s[i+k]==s[sa[rank[i]-1]+k])
++k;
h[rank[i]]=k;
if(h[rank[i]]>ans1)
{
ans1=h[rank[i]];
pos1=i;
}
}
return str.substr(pos1,ans1);
}
int main()
{
string s;
while(cin>>s)
{
s=duplicate_substr(s);
printf("%d
",s.length()+1);
}
return 0;
}
BOJ478 막내 여동생 버섯 따기 수학 문제
원하는 기하학적 개형을 이용하여 문제풀이: 첫 번째 버섯은 반드시 새 버섯이고, 두 번째 버섯은 (n-1)/n의 확률로 새 버섯을 얻으면 한 번에 (n-1)/n의 새 버섯을 얻었다고 볼 수 있으며, 새 버섯을 얻은 횟수는 n/(n-1)이다.새 버섯을 처음 구할 때의 기대는 n/(n-S)
그룹수+고수+수열지식을 이용하여: 지금 우리가 S개의 버섯을 얻었다고 가정하면 다음에 새 버섯을 얻을 확률은 (n-S)/n이고, 늙은 버섯을 얻을 확률은 S/n:
처음 새로운 버섯을 얻는 기대는 1*(n-S)/n;
두 번째로 새 버섯을 얻는 기대는 2*(n-S)/n*(S/n)^1;
세 번째로 새 버섯을 얻는 기대는 3*(n-S)/n*(S/n)^2;
....
무한대로 커질 때(수열의 오차가 상감하고 극한을 취하는 방법으로 알 수 있듯이 S번에 새 버섯을 얻는 기대는 n/(n-S)#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n) {
if(n < 0) {
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n) {
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------------------------------------------
double dp[111];
int main()
{
int n;
while(read(n))
{
memset(dp,0.0,sizeof(dp));
for(int i=1;i<=n;i++)
{
dp[i]=dp[i-1]+(double)(n)/(double)(n-i+1);
}
printf("%.6f
",dp[n]);
}
return 0;
}
BOJ482 초점급 긴 레이저포 이분도의 가장 일치
n개의 레이저포를 n*m 점으로 분해하는 것은 각 점의 i차 발사 소모 시간(최대 m회 발사
첫 번째 점 해체 후의 점을 예로 삼아 그림을 만든다. 첫 번째 대포와 목표점의 권한은 T1(분 단위로 변환)+직선거리/속도이다.
두 번째 발포와 목표점의 권한은 -2*T1(분단위로 변환) + T2 + 직선거리/속도(이런 식으로 추정된다
그리고 2분 동안 그림+증폭로(가지를 자르지 않으면 TLE#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define CLR(x,y) memset(x,y,sizeof(x))
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
const int MAXN=60;
struct Point
{
int x,y;
}a[MAXN],b[MAXN];
struct Edge
{
int to,next;
int val;
}e[MAXN*MAXN*MAXN];
int n,m,t,t2,v;
double w[MAXN*MAXN][MAXN];
int head[MAXN*MAXN],pre[MAXN*MAXN],idx;
bool vis[MAXN*MAXN];
void add_edge(int u,int v)
{
e[idx].to=v;
e[idx].next=head[u];
head[u]=idx++;
}
void make_graph(double limit)
{
idx=0;
CLR(head,-1);
CLR(pre,-1);
for(int i=0;i<n*m;i++)
for(int j=0;j<m;j++)
if(w[i][j]<=limit)
add_edge(i,j);
}
bool dfs(int u)
{
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
if(!vis[v])
{
vis[v]=true;
if(pre[v]==-1 || dfs(pre[v]))
{
pre[v]=u;
return true;
}
}
}
return false;
}
double dist(int x,int y,int xx,int yy)
{
return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy))/(double)v;
}
int main()
{
// freopen("data.txt","r",stdin);
while(read(n)&&read(m)&&read(t)&&read(t2)&&read(v))
{
double t1=(double)t/60.0;
for(int i=0;i<m;i++)
read(b[i].x),read(b[i].y);
for(int i=0;i<n;i++)
read(a[i].x),read(a[i].y);
for(int i=0;i<n;i++) // I
{
for(int j=0;j<m;j++) // J
{
int temp=i*m;
w[temp][j]=dist(a[i].x,a[i].y,b[j].x,b[j].y)+t1; //
// cout<<i<<" "<<j<<" : "<<dis<<endl;
for(int k=1;k<m;k++) // K
w[temp+k][j]=w[temp+k-1][j]+t1+t2;
}
}
/*
for(int i=0;i<n*m;i++)
{
for(int j=0;j<m;j++)
cout<<w[i][j]<<" ";
cout<<endl;
}
*/
double b_low=0,b_high=(1<<31)-1,b_mid;
double ans=0;
int time=100;
while(time--)
{
b_mid=b_low+(b_high-b_low)/2;
make_graph(b_mid);
int temp=0;
for(int i=0;i<n*m&&temp!=m;i++)
{
CLR(vis,0);
if(dfs(i))
temp++;
}
if(temp==m)
{
ans=b_mid;
b_high=b_mid;
}
else
b_low=b_mid;
}
printf("%.6f
",ans+1e-7);
}
return 0;
}
BOJ489 동생이 배를 저으러 갔어요. 시뮬레이션 문제
종점 에서 기점 을 빼고 차치 에 따라 풍향 을 결정 하다#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
//-----------------------------------------------------------------------
const int MAXN=100010;
ll t,sx,sy,ex,ey;
char str[MAXN];
int main()
{
// freopen("data.txt","r",stdin);
while(read(t)&&read(sx)&&read(sy)&&read(ex)&&read(ey))
{
ll tx=ex-sx,ty=ey-sy;
int time=0;
gets(str);
for(int i=0;i<t;i++)
{
if(str[i]=='S'&&ty<0)
ty++;
else if(str[i]=='E'&&tx>0)
tx--;
else if(str[i]=='N'&&ty>0)
ty--;
else if(str[i]=='W'&&tx<0)
tx++;
time++;
if(!tx&&!ty)
break;
}
if(!tx&&!ty)
printf("%d
",time);
else
printf("-1
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <cstdio>
const long long MAX = 1000000100;
const long long N = 1000000000;
const long long BASE = 10000;
bool used[MAX];
int main(void)
{
freopen("out.txt","w",stdout);
int cnt = 0;
for(long long i = 2; i <= N; ++i){
if(!used[i]){
cnt++;
for(long long j = i *i; j <= N; j += i)
used[j] = true;
}
if(i % BASE == 0)
printf("%d,",cnt);
}
return 0;
}
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1;
char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
bool Prime(int x)
{
if (x == 1)
return false;
else if (x <= 0)
return false;
else if (x == 2)
return true;
else
{
for(ll i = 2; i*i <= x; i++)
if (x%i == 0)
return false;
return true;
}
}
const long long MAX = 1000000100;
const long long N = 1000000000;
const long long BASE = 10000;
int a[]= {};
int main()
{
int n;
// freopen("data.txt","r",stdin);
while(read(n))
{
int temp=n/BASE;
int ans;
if(temp==0)
ans=0;
else
ans=a[temp-1];
for(int i=BASE*temp; i<=n; i++)
if(Prime(i))
ans++;
printf("%d
",ans);
}
return 0;
}
최대 반복 하위 문자열 길이 +1
모범 문제로 풀 수 있는데, 어쨌든 방법이 유난히 많죠.
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n) {
if(n < 0) {
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n) {
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------------------------------------------
const int MAXN=1000010;
void radix(int *str,int *a,int *b,int n,int m)
{
static int count[MAXN];
memset(count,0,sizeof(count));
for(int i=0;i<n;++i)
++count[str[a[i]]];
for(int i=1;i<=m;++i)
count[i]+=count[i-1];
for(int i=n-1;i>=0;--i)
b[--count[str[a[i]]]]=a[i];
}
void suffix_array(int *str,int *sa,int n,int m)
{
static int rank[MAXN],a[MAXN],b[MAXN];
for(int i=0;i<n;i++)
rank[i]=i;
radix(str,rank,sa,n,m);
rank[sa[0]]=0;
for(int i=1;i<n;i++)
rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
for(int i=0;1<<i <n;++i)
{
for(int j=0;j<n;++j)
{
a[j]=rank[j]+1;
b[j]=j +(1<<i)>=n? 0:rank[j+(1<<i)] +1;
sa[j]=j;
}
radix(b,sa,rank,n,n);
radix(a,rank,sa,n,n);
rank[sa[0]]=0;
for(int j=1;j<n;j++)
{
rank[sa[j]]=rank[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]);
}
}
}
string duplicate_substr(string str)
{
string rev;
static int s[MAXN],sa[MAXN],rank[MAXN],h[MAXN];
int n=str.length();
copy(str.begin(),str.end(),s);
suffix_array(s,sa,n,256);
for(int i=0;i<n;++i)
rank[sa[i]]=i;
int k=0;
int ans1=0,pos1=0;
for(int i=0;i<n;i++)
{
k= k==0? 0:k-1;
while(rank[i]>0&&s[i+k]==s[sa[rank[i]-1]+k])
++k;
h[rank[i]]=k;
if(h[rank[i]]>ans1)
{
ans1=h[rank[i]];
pos1=i;
}
}
return str.substr(pos1,ans1);
}
int main()
{
string s;
while(cin>>s)
{
s=duplicate_substr(s);
printf("%d
",s.length()+1);
}
return 0;
}BOJ478 막내 여동생 버섯 따기 수학 문제
원하는 기하학적 개형을 이용하여 문제풀이: 첫 번째 버섯은 반드시 새 버섯이고, 두 번째 버섯은 (n-1)/n의 확률로 새 버섯을 얻으면 한 번에 (n-1)/n의 새 버섯을 얻었다고 볼 수 있으며, 새 버섯을 얻은 횟수는 n/(n-1)이다.새 버섯을 처음 구할 때의 기대는 n/(n-S)
그룹수+고수+수열지식을 이용하여: 지금 우리가 S개의 버섯을 얻었다고 가정하면 다음에 새 버섯을 얻을 확률은 (n-S)/n이고, 늙은 버섯을 얻을 확률은 S/n:
처음 새로운 버섯을 얻는 기대는 1*(n-S)/n;
두 번째로 새 버섯을 얻는 기대는 2*(n-S)/n*(S/n)^1;
세 번째로 새 버섯을 얻는 기대는 3*(n-S)/n*(S/n)^2;
....
무한대로 커질 때(수열의 오차가 상감하고 극한을 취하는 방법으로 알 수 있듯이 S번에 새 버섯을 얻는 기대는 n/(n-S)#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n) {
if(n < 0) {
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n) {
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------------------------------------------
double dp[111];
int main()
{
int n;
while(read(n))
{
memset(dp,0.0,sizeof(dp));
for(int i=1;i<=n;i++)
{
dp[i]=dp[i-1]+(double)(n)/(double)(n-i+1);
}
printf("%.6f
",dp[n]);
}
return 0;
}
BOJ482 초점급 긴 레이저포 이분도의 가장 일치
n개의 레이저포를 n*m 점으로 분해하는 것은 각 점의 i차 발사 소모 시간(최대 m회 발사
첫 번째 점 해체 후의 점을 예로 삼아 그림을 만든다. 첫 번째 대포와 목표점의 권한은 T1(분 단위로 변환)+직선거리/속도이다.
두 번째 발포와 목표점의 권한은 -2*T1(분단위로 변환) + T2 + 직선거리/속도(이런 식으로 추정된다
그리고 2분 동안 그림+증폭로(가지를 자르지 않으면 TLE#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define CLR(x,y) memset(x,y,sizeof(x))
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
const int MAXN=60;
struct Point
{
int x,y;
}a[MAXN],b[MAXN];
struct Edge
{
int to,next;
int val;
}e[MAXN*MAXN*MAXN];
int n,m,t,t2,v;
double w[MAXN*MAXN][MAXN];
int head[MAXN*MAXN],pre[MAXN*MAXN],idx;
bool vis[MAXN*MAXN];
void add_edge(int u,int v)
{
e[idx].to=v;
e[idx].next=head[u];
head[u]=idx++;
}
void make_graph(double limit)
{
idx=0;
CLR(head,-1);
CLR(pre,-1);
for(int i=0;i<n*m;i++)
for(int j=0;j<m;j++)
if(w[i][j]<=limit)
add_edge(i,j);
}
bool dfs(int u)
{
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
if(!vis[v])
{
vis[v]=true;
if(pre[v]==-1 || dfs(pre[v]))
{
pre[v]=u;
return true;
}
}
}
return false;
}
double dist(int x,int y,int xx,int yy)
{
return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy))/(double)v;
}
int main()
{
// freopen("data.txt","r",stdin);
while(read(n)&&read(m)&&read(t)&&read(t2)&&read(v))
{
double t1=(double)t/60.0;
for(int i=0;i<m;i++)
read(b[i].x),read(b[i].y);
for(int i=0;i<n;i++)
read(a[i].x),read(a[i].y);
for(int i=0;i<n;i++) // I
{
for(int j=0;j<m;j++) // J
{
int temp=i*m;
w[temp][j]=dist(a[i].x,a[i].y,b[j].x,b[j].y)+t1; //
// cout<<i<<" "<<j<<" : "<<dis<<endl;
for(int k=1;k<m;k++) // K
w[temp+k][j]=w[temp+k-1][j]+t1+t2;
}
}
/*
for(int i=0;i<n*m;i++)
{
for(int j=0;j<m;j++)
cout<<w[i][j]<<" ";
cout<<endl;
}
*/
double b_low=0,b_high=(1<<31)-1,b_mid;
double ans=0;
int time=100;
while(time--)
{
b_mid=b_low+(b_high-b_low)/2;
make_graph(b_mid);
int temp=0;
for(int i=0;i<n*m&&temp!=m;i++)
{
CLR(vis,0);
if(dfs(i))
temp++;
}
if(temp==m)
{
ans=b_mid;
b_high=b_mid;
}
else
b_low=b_mid;
}
printf("%.6f
",ans+1e-7);
}
return 0;
}
BOJ489 동생이 배를 저으러 갔어요. 시뮬레이션 문제
종점 에서 기점 을 빼고 차치 에 따라 풍향 을 결정 하다#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
//-----------------------------------------------------------------------
const int MAXN=100010;
ll t,sx,sy,ex,ey;
char str[MAXN];
int main()
{
// freopen("data.txt","r",stdin);
while(read(t)&&read(sx)&&read(sy)&&read(ex)&&read(ey))
{
ll tx=ex-sx,ty=ey-sy;
int time=0;
gets(str);
for(int i=0;i<t;i++)
{
if(str[i]=='S'&&ty<0)
ty++;
else if(str[i]=='E'&&tx>0)
tx--;
else if(str[i]=='N'&&ty>0)
ty--;
else if(str[i]=='W'&&tx<0)
tx++;
time++;
if(!tx&&!ty)
break;
}
if(!tx&&!ty)
printf("%d
",time);
else
printf("-1
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n) {
if(n < 0) {
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n) {
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------------------------------------------
double dp[111];
int main()
{
int n;
while(read(n))
{
memset(dp,0.0,sizeof(dp));
for(int i=1;i<=n;i++)
{
dp[i]=dp[i-1]+(double)(n)/(double)(n-i+1);
}
printf("%.6f
",dp[n]);
}
return 0;
}n개의 레이저포를 n*m 점으로 분해하는 것은 각 점의 i차 발사 소모 시간(최대 m회 발사
첫 번째 점 해체 후의 점을 예로 삼아 그림을 만든다. 첫 번째 대포와 목표점의 권한은 T1(분 단위로 변환)+직선거리/속도이다.
두 번째 발포와 목표점의 권한은 -2*T1(분단위로 변환) + T2 + 직선거리/속도(이런 식으로 추정된다
그리고 2분 동안 그림+증폭로(가지를 자르지 않으면 TLE
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define CLR(x,y) memset(x,y,sizeof(x))
#define eps 1e-9
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
const int MAXN=60;
struct Point
{
int x,y;
}a[MAXN],b[MAXN];
struct Edge
{
int to,next;
int val;
}e[MAXN*MAXN*MAXN];
int n,m,t,t2,v;
double w[MAXN*MAXN][MAXN];
int head[MAXN*MAXN],pre[MAXN*MAXN],idx;
bool vis[MAXN*MAXN];
void add_edge(int u,int v)
{
e[idx].to=v;
e[idx].next=head[u];
head[u]=idx++;
}
void make_graph(double limit)
{
idx=0;
CLR(head,-1);
CLR(pre,-1);
for(int i=0;i<n*m;i++)
for(int j=0;j<m;j++)
if(w[i][j]<=limit)
add_edge(i,j);
}
bool dfs(int u)
{
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
if(!vis[v])
{
vis[v]=true;
if(pre[v]==-1 || dfs(pre[v]))
{
pre[v]=u;
return true;
}
}
}
return false;
}
double dist(int x,int y,int xx,int yy)
{
return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy))/(double)v;
}
int main()
{
// freopen("data.txt","r",stdin);
while(read(n)&&read(m)&&read(t)&&read(t2)&&read(v))
{
double t1=(double)t/60.0;
for(int i=0;i<m;i++)
read(b[i].x),read(b[i].y);
for(int i=0;i<n;i++)
read(a[i].x),read(a[i].y);
for(int i=0;i<n;i++) // I
{
for(int j=0;j<m;j++) // J
{
int temp=i*m;
w[temp][j]=dist(a[i].x,a[i].y,b[j].x,b[j].y)+t1; //
// cout<<i<<" "<<j<<" : "<<dis<<endl;
for(int k=1;k<m;k++) // K
w[temp+k][j]=w[temp+k-1][j]+t1+t2;
}
}
/*
for(int i=0;i<n*m;i++)
{
for(int j=0;j<m;j++)
cout<<w[i][j]<<" ";
cout<<endl;
}
*/
double b_low=0,b_high=(1<<31)-1,b_mid;
double ans=0;
int time=100;
while(time--)
{
b_mid=b_low+(b_high-b_low)/2;
make_graph(b_mid);
int temp=0;
for(int i=0;i<n*m&&temp!=m;i++)
{
CLR(vis,0);
if(dfs(i))
temp++;
}
if(temp==m)
{
ans=b_mid;
b_high=b_mid;
}
else
b_low=b_mid;
}
printf("%.6f
",ans+1e-7);
}
return 0;
}
BOJ489 동생이 배를 저으러 갔어요. 시뮬레이션 문제
종점 에서 기점 을 빼고 차치 에 따라 풍향 을 결정 하다#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
//-----------------------------------------------------------------------
const int MAXN=100010;
ll t,sx,sy,ex,ey;
char str[MAXN];
int main()
{
// freopen("data.txt","r",stdin);
while(read(t)&&read(sx)&&read(sy)&&read(ex)&&read(ey))
{
ll tx=ex-sx,ty=ey-sy;
int time=0;
gets(str);
for(int i=0;i<t;i++)
{
if(str[i]=='S'&&ty<0)
ty++;
else if(str[i]=='E'&&tx>0)
tx--;
else if(str[i]=='N'&&ty>0)
ty--;
else if(str[i]=='W'&&tx<0)
tx++;
time++;
if(!tx&&!ty)
break;
}
if(!tx&&!ty)
printf("%d
",time);
else
printf("-1
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1; char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
//-----------------------------------------------------------------------
const int MAXN=100010;
ll t,sx,sy,ex,ey;
char str[MAXN];
int main()
{
// freopen("data.txt","r",stdin);
while(read(t)&&read(sx)&&read(sy)&&read(ex)&&read(ey))
{
ll tx=ex-sx,ty=ey-sy;
int time=0;
gets(str);
for(int i=0;i<t;i++)
{
if(str[i]=='S'&&ty<0)
ty++;
else if(str[i]=='E'&&tx>0)
tx--;
else if(str[i]=='N'&&ty>0)
ty--;
else if(str[i]=='W'&&tx<0)
tx++;
time++;
if(!tx&&!ty)
break;
}
if(!tx&&!ty)
printf("%d
",time);
else
printf("-1
");
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
