Codeforces Round #338 (Div. 2)

제목 링크:http://codeforces.com/contest/615
첫 번 째 문제:
간단 하 다

#include<bits/stdc++.h>
using namespace std;
int nn[140];
int main(){
    int n,m;
    while(cin>>n>>m){
    memset(nn,0,sizeof(nn));
    for(int i = 0;i<n;i++){
    int a;
    cin>>a;
        for(int j = 0;j<a;j++){
            int b;
            cin>>b;
            b--;
            nn[b] = 1;
        }
    }int ans = 0;
    for(int i = 0;i<m;i++){
        if(nn[i] == 1)ans++;
    }
    if(ans==m)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    }


}

두 번 째 문제: 나 같은 영어 쓰레기 에 대해 서 는 제목 의 뜻 이 너무 이해 하기 어렵다.어렵 지 않 아 요.
제목:
종이 위 에 n 개의 점, m 개의 변 의 무방 향도 가 있 고 자신의 변 을 가리 키 지 않 는 다.엄 격 히 증가 하 는 연 결 된 노선 을 찾 아 이 노선 의 포 인 트 를 기록 하고 이 노선 의 끝 에서 가장 큰 점 은 며칠 동안 인접 한 변 b 를 기록 하 며 a 를 구한다.×b 의 최대 치.
문제 풀이 방향:
동적 계획 의 사상 을 이용 하여 dp [i] = max (dp [i], dp [j] + 1) 그 중에서 j < i, 그리고 (i, j) 가 연결 되 어 있 으 면 끝 이 i 인 tail 의 최대 길 이 를 구 할 수 있 습 니 다.그리고 그것 의 spines 는 i 와 연 결 된 점 의 개수 이다.양자 상승의 최대 치 를 구하 다.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100050;
typedef long long ll;
vector<int>V[maxn];
int dp[maxn];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i = 0;i<m;i++){
		int a,b;
		cin>>a>>b;
		V[a].push_back(b);
		V[b].push_back(a);
	}
	memset(dp,0,sizeof(dp));
	dp[1] = 1;ll ans = 1;
	for(int i = 1;i<=n;i++){
		dp[i] = 1;
		for(int j = 0;j<V[i].size();j++){
			if(i>V[i][j]){
				dp[i] = max(dp[i],dp[V[i][j]]+1);
			}
		}
		int t  = V[i].size();
		//cout<<t<<" "<<dp[i]<<endl;
		ans = max(ans,1ll*dp[i]*t);
	}
	cout<<ans<<endl;


}

세 번 째 문제: 이 문 제 는 잘못된 생각 에 들 어가 경기 가 끝 난 후에 wa 가 떨 어 졌 다.
제목: 문자열 a, b 두 개 주세요.a 또는 reverse (a) 에서 k 개의 문자열 을 캡 처 하여 이 문자열 을 b 문자열 로 연결 시 키 고 k 의 최소 값 을 구하 고 문자열 의 시작 x 와 종료 위치 y 를 출력 합 니 다.a 의 x < y, reverse (a) 에서 x > y.b 로 연결 되 지 않 으 면 출력 - 1.
문제 풀이 방향:
맞 출 수 없 을 때 b 에 a 에 없 는 알파벳 을 포함 합 니 다.
시간 을 맞 출 수 있다

ans = 0
for i in b:
    ma = 0
    for j in a:
        cnt = 0;ii = i;jj = j(1)
        while ii == jj:      (2)
            ii++;jj++;cnt++  (3)
        ma = max(ma,cnt)
    for j  in reverse(a):
        (1)(2)(3)
    i+=ma-1;ans++
print ans

ma 는 한 번 의 문자열 의 최대 길이 입 니 다. cnct 는 매번 대비 하 는 최대 길이 입 니 다. ans 는 문자열 의 세그먼트 수 입 니 다. 그리고 jj - ma + 1 과 jj 를 기록 하 십시오.

#include<bits/stdc++.h>
using namespace std;
int aa[27];
int bb[27];
int qi[2500];
int ho[2500];
int main(){
	string a,ar,b;
	cin>>a;
	cin>>b;
	ar = a;
	reverse(ar.begin(),ar.end());
	int al = a.size();
	int bl = b.size();
	for(int i = 0;i<al;i++)aa[a[i]-'a'] = 1;
	for(int i = 0;i<bl;i++)bb[b[i]-'a'] = 1;
	for(int i  = 0;i<26;i++){
		if(aa[i]==0&&bb[i]==1){cout<<"-1"<<endl;return 0;}
	}
	int ans = 0;
	for(int i = 0;i<bl;i++){
	int ma = 0,ma1=  0;
		for(int j = 0;j<al;j++){
			int ii = i;int cnt = 0;int yn = 0;int jj = j;
			while(b[ii] == a[jj]){ii++;jj++;cnt++;if(ii>=bl)break;if(jj>= al)break;yn = 1;}
			ma1 = max(ma,cnt);
			if(ma1 !=ma){qi[ans] = jj-ma1+1;ho[ans] = jj;}
			ma = ma1;
		}
		for(int j = 0;j<al;j++){
			int ii = i;int cnt = 0;int yn = 0;int jj = j;
			while(b[ii] == ar[jj]){ii++;jj++;cnt++;if(ii>=bl)break;if(jj>= al)break;yn = 1;}
			ma1 = max(ma,cnt);
			if(ma1 !=ma){qi[ans] = jj;ho[ans] = jj-ma1+1;}
			ma = ma1;
		}
		i+=ma-1;
		ans++;
	}
	cout<<ans<<endl;
	for(int i = 0;i<ans;i++){
		cout<<qi[i]<<" "<<ho[i]<<endl;
	}
	return 0;
}

네 번 째 문제: 수준 이 너무 낮 아서 경기 할 때 할 줄 모른다.
제목: n 의 각 질 수 를 주 고 n 의 각 질 수 를 곱 한 값 m 의 모든 인자 의 곱 하기 mod (1e9 + 7) 를 구하 십시오.예 를 들 어 3 개의 질 수 를 제시 하 다. 2, 2, 3.곱 하기 12.양보 하 다×2×3×4×6×12mod (1e9 + 7) 의 값 입 니 다.
문제 풀이 방향:
20000 이하 의 소 수 는 많 지 않 기 때문에 중복 되 는 숫자 가 많 을 것 이다.소수 와 대응 하 는 개 수 를 기록 하기 위해 맵 을 엽 니 다.
그 다음 에 조합 상황 을 보면 소수 j 에 k 개가 있다 고 가정 하면 j 는 (kj + 1) 가지 형식 이 있 기 때문에 모든 소수 에 대해 (k1 + 1) 가 있다.×（k2+1）×（k3+1）×(k4 + 1) *... * (kn + 1) = sum 종 조합 방식.j 를 고려 하지 않 을 때 sum / (kj + 1) 종이 있 습 니 다.그 중 하 나 를 j 를 제외 한 곱 하기 가 a 라 고 가정 하면 (a)×（a×j）×（a× j^2）×（a×j^3）×...×（a×j^kj） = （a^(kj+1)）×(j ^ (kj * (kj + 1) / 2). 그래서 모든 상황 에서 j ^ ((kj * (kj + 1) / 2) 를 곱 했다.
그러나 데이터 양 이 너무 많 으 면 sum 이 log 를 폭발 시 킬 수 있 기 때문에 모든 j 의 sum / (kj + 1) 를 풀 때 방법 을 생각해 야 합 니 다.
우 리 는 cnct (j) 로 j ^ ((kj * (kj + 1) / 2) 를 표시 합 니 다.
그래서 우 리 는 d 로 j 에 옮 겨 다 닐 때의 종 류 를 표시 합 니 다. 즉, d (j) = (k1 + 1)×（k2+1）×（k3+1）×...×（kj+1）
그리고

d(0)=1;ans = 1;
for j in ma:
    cnt(j)
    ans=ans^(k+1)*cnt(j)^d（j-1）;
    d(j)
ans     

         2 2 3 5 5   cnt(1) = 2^(2*3/2)=8,cnt(2)=3^(1+2/2)cnt(3)
j = 1:
    ans = cnt(1)^1
    d(1)=d(0)*(k1+1)=(k1+1)
j = 2:
    ans = cnt(1)^1^(k2+1)*cnt(2)^(k1+1)
    d(2) =d(1)*(k2+1)= (k1+1)*(k2+1)
j = 3:
    ans = cnt(1)^1^(k2+1)^(k3+1)*cnt(2)^(k1+1)(k3+1)*cnt(3)^(k1+1)*(k2+1)
    d(3) = d(2)*(k3+1)
 그리고 본 해법 에는 sum / k 의 연산 이 없다.페 르 마 의 작은 정리 에 따 르 면 p 가 질 수 이 고 gcd (a, p) = 1 이 라면 a ^ (p - 1), 1 (mod p) 은 a ^ x, 1 a ^ (x% (m - 1) (mod p) 이기 때문에% mod 를 더 해 얻 을 수 있다. d(0)=1;ans = 1;
for j in ma:
    cnt(j)
    ans=ans^(k+1)%mod*cnt(j)^d（j-1）%mod;
    d(j)%（mod-1）
         
 ll fast_mod(ll n,ll m,ll mod){
	ll ans =1;
	while(m){
		if(m&1)ans = ans*n%mod;
		m>>=1;
		n = n*n%mod;
	}
	return ans;
}
 는 ans 를 신속하게 풀 수 있다.#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p[200050];
map<int ,ll>MA;
const ll mod = 1e9+7;
ll fast_mod(ll n,ll m,ll mod){
	ll ans =1;
	while(m){
		if(m&1)ans = ans*n%mod;
		m>>=1;
		n = n*n%mod;
	}
	return ans;
}
int main(){
	int T;
	cin>>T;
	MA.clear();
	for(int i = 0;i<T;i++){
		int a;
		scanf("%d",&a);
		MA[a]++;
	}
	map<int,ll>::iterator it;
	ll sum = 1;
	ll ans = 1;
	for(it = MA.begin();it!=MA.end();it++){
		int cnt = fast_mod(it->first,(it->second+1)*it->second/2,mod);
		ans=fast_mod(ans,it->second+1,mod)*fast_mod(cnt,sum,mod)%mod;
		sum=sum*(it->second+1)%(mod-1);
	}
	printf("%I64d
",ans);
}
  
다섯 번 째 문제: 공식 을 찾 아??
문제 풀이:
우 리 는 예 를 들 어 밖으로 6 단계 씩 증가 하 는 것 을 발견 했다. 그래서 우 리 는 걸음 수 k 를 제시 하 는 층수 N 을 구 할 수 있다.
그런 후에 우 리 는 각 층 에 여섯 개의 변 이 있 고 모든 변 의 걸음 수 는 층수 N 이라는 것 을 발견 했다.
우 리 는 걸음 수 k 의 층수 N, 변 수 bian, 그리고 이 변 에 있 는 몇 번 째 ge 를 구 할 수 있다.
그리고 좌표 에 따라 해 를 구한다.#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll n;
	cin>>n;
	if(n == 0){cout<<"0 0"<<endl;return 0;}
	//int x,int y;
	//cout<<"n"<<n<<endl;
	ll nn =(n+5)/6;
	ll ns = sqrt(nn*2);
	while(ns*(ns+1)/2<nn)ns++;
	ns--;
//cout<<ns<<endl;//     
	ll cnt,bian,ge;
		 cnt = n-ns*(ns+1)/2*6-1;
		bian = cnt/(ns+1);
		ge = cnt%(ns+1);
	ll cx,cy;
	ll x,y;
	ge++;ns++;
	if(bian == 0){
	cx = 2*ns;cy = 0;
		x = cx-ge;
		y = cy+ge*2;
	}
	if(bian == 1){
		cx = ns,cy =2*ns;
		x = cx-ge*2;
		y = cy;
	}
	if(bian == 2){
		cx = -ns,cy =2*ns;
		x = cx-ge;
		y = cy-ge*2;
	}
	if(bian == 3){
		cx = -ns*2,cy =0;
		x = cx+ge;
		y = cy-ge*2;
	}
	if(bian == 4){
		cx = -ns,cy =-2*ns;
		x = cx+ge*2;
		y = cy;
	}
	if(bian == 5){
		cx = ns,cy =-2*ns;
		x = cx+ge;
		y = cy+ge*2;
	}
	cout<<x<<" "<<y<<endl;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형

구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Codeforces Round #338 (Div. 2)

좋은 웹페이지 즐겨찾기