2016 '바 이 두 의 별' - 1 차 전 (Astar Round2A)
Accepts: 1281
Submissions: 7580
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
F(x, m)F(x,m) 모두 숫자 xx 로 구 성 된 mm 비트 숫자 를 대표 합 니 다.다음 식 이 성립 되 었 는 지 계산 하 십시오.
F(x,m)\mod\k\\equiv\cF(x,m) mod k ≡ c
Input
첫 번 째 줄 의 정수 TT 는 TT 팀 의 데 이 터 를 나타 낸다.각 그룹의 테스트 데 이 터 는 한 줄 을 차지 하고 네 개의 숫자 x, m, k, cx, m, k, c 를 포함한다.
1\leq x\leq 91≤x≤9
1\leq m\leq 10^{10}1≤m≤1010
0\leq c< k\leq 10,0000≤c
각 그룹의 데이터 에 대해 두 줄 을 출력 합 니 다. 첫 번 째 줄 의 출력: "Case\# i:".ii 는 ii 조 테스트 데 이 터 를 대표 합 니 다.두 번 째 줄 은 'Yes' 나' No '를 출력 하고 네 개의 숫자 를 대표 하 며 제목 에서 준 공식 을 만족 시 킬 수 있 습 니까?
Sample Input
3
1 3 5 2
1 3 5 1
3 5 99 69
Sample Output
Case #1:
No
Case #2:
Yes
Case #3:
Yes
Hint
对于第一组测试数据：111 mod 5 = 1，公式不成立，所以答案是”No”，而第二组测试数据中满足如上公式，所以答案是 “Yes”。
문제 풀이: 서랍 의 원 리 는 k 가 최대 10000 이기 때문에 최대 10000 번 모드 를 가 진 후에 반드시 순환 절 이 나타 날 것 이다.
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <map>
#include <string.h>
using namespace std;
typedef long long ll;
map<int,int> mp;
vector<int> vec;
int main()
{
int T,cnt = 0;
ll x,m,k,c;
cin >> T;
while(T--)
{
mp.clear();
vec.clear();
cin >> x >> m >> k >> c;
ll tp = 0;
int ans = -1;
for(int i = 1; i <= m; ++i)
{
tp = tp * 10 + x;
tp %= k;
// cout << tp << endl;
if(mp[tp])
{
int len = i - mp[tp];
m -= mp[tp] - 1;
m %= len;
if(m == 0) ans = vec[vec.size() - 1];
else ans = vec[mp[tp] + m - 1];
break;
}
vec.push_back(tp);
mp[tp] = i;
}
if(ans == -1) ans = vec[m - 1];
printf("Case #%d:
",++cnt);
puts(ans == c ? "Yes" : "No");
}
return 0;
}BD String
Accepts: 388
Submissions: 1164
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
알다 시 피 도 곰 이 좋아 하 는 문 자 는 B 와 D 밖 에 없다.
오늘 은 B 와 D 로 문자열 을 구성 하 는 규칙 을 발 명 했 습 니 다.
S(1)=BS(1)=B
S(2)=BBDS(2)=BBD
S(3)=BBDBBDDS(3)=BBDBBDD
…
S(n)=S(n-1)+B+reverse(flip(S(n-1))S(n)=S(n−1)+B+reverse(flip(S(n−1))
그 중에서 reverse (s) reverse (s) 는 문자열 을 뒤 집 는 것 을 말한다. 예 를 들 어 reverse (BBD) = DBBreverse (BBD) = DBB, flip (s) flip (s) 은 문자열 중의 BB 를 DD 로 바 꾸 고 DD 는 BB 로 바 꾸 는 것 을 말한다. 예 를 들 어 flip (BBD) = DDBflip (BBD) = DDB 이다.
도 도 곰 은 평소 컴퓨터 로 만 연속적으로 보 았 지만 이 기계 의 비 길 데 없 는 연산 속 도 를 방해 하지 않 았 다. 현재 S (2 ^ {1000}) S (2 1000) 의 내용 을 계산 해 냈 지만 도 곰 은 곰 일 뿐 이렇게 긴 문자열 을 한 번 에 읽 을 수 없다. 이 문자열 의 제 LL 위 (1 부터) 를 알 고 싶다.RR 위 까지 들 어 있 는 BB 의 개 수 는 얼마 입 니까?
Input
첫 번 째 줄 의 정수 TT 는 T (1\\leq T\\leq 1000) T (1 ≤ T ≤ 1000) 를 나타 낸다. 그룹 데이터.
각 그룹의 데 이 터 는 두 개의 수 LL 과 R (1\\leq L\\leq R\\leq 10 ^ {18}) R (1 ≤ L ≤ R ≤ 10 18) 을 포함한다. .
Output
각 그룹의 데이터 에 대해 S (2 ^ {1000}) S (2 1000) 가 표시 하 는 문자열 의 LL 위 에서 RR 위 에서 BB 의 개 수 를 출력 합 니 다.
Sample Input
3
1 3
1 7
4 8
Sample Output
2
4
3
문제 풀이: S (n) = S (n - 1) + B + reverse (flip (S (n - 1))) 에서 S (n) 를 알 수 있다.가짜 리 턴 문자열 을 위해 플 립 동작 이 없 으 면 리 턴 문자열 입 니 다. 리 턴 문자열 의 정의 에 따 르 면 mid 좌우 양쪽 의 B 수 는 같 습 니 다. 좌우 거리 mid 가 같은 경우 이 특성 으로 구간 을 나 눌 수 있 습 니 다. 두 가지 로 나 누 어 볼 때 L, R 이 mid 오른쪽 에 있 으 면 구간 을 mid 왼쪽 에 비 출 수 있 습 니 다. 이때 B 수 를 구 하 는 것 은 D 수 에 해당 합 니 다.플 립 작업 때문에, 만약 L < = mid & & R > = mid 라면, mid 좌우 양쪽 에서 같은 길이 의 구간 을 취 할 수 있 고, 나머지 구간 은 mid 의 왼쪽 인지 오른쪽 인지 고려 하고 있 으 며, 오른쪽 이 라면 매 핑 을 해서 D 의 수량 으로 바 꿀 수 있 습 니 다. 따라서 전체 알고리즘 은 최대 60 층 까지 만 재 귀적 하면 해 제 됩 니 다. 시간 복잡 도 는 log (R - L + 1) 입 니 다.
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll dfs(ll l,ll r,int v)
{
ll tp = 0,cnt = 0,mid;
for(int i = 1; ; ++i)
{
mid = tp + 1;
tp = tp * 2 + 1;
if(tp >= r) break;
}
if(l <= mid && r >= mid)
{
if(mid - l > r - mid)
{
if(v == 0) cnt++;
cnt += r - mid;
cnt += dfs(l,2 * mid - r - 1,v);
}
else if(mid - l < r - mid)
{
if(v == 0) cnt++;
cnt += mid - l;
l = 2 * mid - l + 1;
cnt += dfs(2 * mid - r,2 * mid - l,v ^ 1);
}
else
{
if(v == 0) cnt++;
cnt += mid - l;
}
}
else if(l > mid)
{
cnt += dfs(2 * mid - r,2 * mid - l,v ^ 1);
}
return cnt;
}
void solve()
{
int T;
cin>>T;
while(T--)
{
ll L,R;
cin >> L >> R;
cout << dfs(L,R,0) << endl;
}
}
int main()
{
solve();
return 0;
}Gym Class
Accepts: 849
Submissions: 4247
Time Limit: 6000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
도도 곰 은 각종 체육 활동 을 좋아 하 는 것 으로 알려 져 있다.
오늘 드디어 꿈 에 그리 던 체육 수업 선생님 이 되 었 습 니 다. 첫 수업 에서 재 미 있 는 일 을 발 견 했 습 니 다. 수업 전에 모든 학우 들 이 일렬 로 서 야 합 니 다. 처음에 모든 사람 에 게 유일한 ID 가 있다 고 가정 하고 1 부터 NN 까지 줄 을 서 면 모든 학우 들 은 자신 을 포함 한 앞 에 있 는 모든 학우 들 의 최소 ID 를 찾 아 자신 이 이 수업 을 평가 하 는 점수 로 삼 습 니 다.수. 귀 찮 은 것 은 어떤 학생 이 그 앞 에 서 는 것 을 원 하지 않 는 다 는 것 이다. 이 전 제 를 만족 시 키 는 상황 에서 신진 체육 과 선생님 인 도 곰 은 마지막 줄 을 서 는 결과 가 모든 학생 들 의 평가 점수 와 최대 가 되 기 를 바란다.
Input
첫 번 째 줄 의 정수 TT 는 T (1\\leq T\\leq 30) T (1 ≤ T ≤ 30) 를 나타 낸다. 그룹 데이터.
각 조 의 데이터 에 대해 첫 번 째 줄 은 두 개의 정수 NN 과 M (1\\leq N\\leq 100000, 0\\leq M\\leq 100000) M (1 ≤ N ≤ 100000, 0 ≤ M ≤ 100000) 을 입력 하여 각각 총 인원수 와 일부 학우 의 선 호 를 나타 낸다.
다음 MM 줄, 줄 당 두 개의 정수 AA. B (1\\leq A, B\leq N) B (1 ≤ A, B ≤ N) 와 ID 가 AA 인 학생 은 ID 가 BB 인 학생 이 그 (그녀) 앞 에 서 는 것 을 원 하지 않 는 다 는 것 을 나타 낸다. 너 는 문제 가 적어도 하나의 배열 방법 이 모든 요구 에 부합 한다 고 생각 할 수 있다.
Output
각 그룹의 데이터 에 대해 최대 점 수 를 출력 합 니 다.
Sample Input
3
1 0
2 1
1 2
3 1
3 1
Sample Output
1
2
6
문제 풀이: 이 문 제 는 욕심 문제 입 니 다. 매번 가장 큰 수 를 앞 에 놓 으 면 된다 는 것 을 알 고 토폴로지 순 서 를 만들어 서 함부로 하면 됩 니 다.
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <string.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
vector<int> vec;
vector<int> G[N];
int in[N];
void topSort(int n)
{
priority_queue<int> que;
for(int i = 1; i <= n; ++i)
{
if(in[i] == 0) que.push(i);
}
while(!que.empty())
{
int tp = que.top();
que.pop();
vec.push_back(tp);
for(int i = 0; i < G[tp].size(); ++i)
{
int v = G[tp][i];
in[v]--;
if(in[v] == 0) que.push(v);
}
}
}
void solve()
{
int T,n,m;
cin >> T;
while(T--)
{
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; ++i) G[i].clear();
vec.clear();
memset(in,0,sizeof in);
for(int i = 0; i < m; ++i)
{
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
in[v]++;
}
topSort(n);
ll ans = 0,Min = n + 1;
for(int i = 0; i < n; ++i)
{
// cout << vec[i] << ' ';
if(vec[i] < Min)
Min = vec[i];
ans += Min;
}
// puts("");
cout << ans << endl;
}
}
int main()
{
solve();
return 0;
}
Close
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
