2019 바 이 두 스타 1 차 전 4 1001 Strassen 1006 Totori 's Switching Game

6951 단어
1001 Strassen
Strassen
Accepts: 567
Submissions: 7005
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
본 문제 에서 우 리 는 단지 두 가지 방법 으로 n 을 계산 할 수 있다.×n 의 행렬 의 곱셈, 첫 번 째 는 정의 법 으로 n3 차 곱셈 과 (n - 1) n2 차 덧셈 이 필요 하 다.두 번 째 는 Strassen 분 치 법 으로 n 이 짝수 일 때 만 사용 할 수 있 으 며 18 (n/2) 2 차 덧셈 과 7 차 크기 를 계산 해 야 한다 (n/2).×(n/2) 의 행렬 의 곱셈.이 7 차 더 작은 행렬 의 곱 하기 도 두 가지 방법 중 하 나 를 선택 하여 계산 할 수 있다.현재 컴퓨터 가 한 번 의 덧셈 을 계산 하 는 데 a 단위 의 시간 이 필요 하 다 고 가정 하고 한 번 의 곱셈 을 계산 하 는 데 b 단위 의 시간 이 필요 하 며 다른 어떠한 조작 도 시간 을 쓰 지 않 고 두 개의 n 을 계산 하 라 고 묻는다.×n 의 행렬 의 곱셈 은 적어도 얼마나 걸 립 니까?출력 정 답 모드 109 + 7 의 나머지 입 니 다.
Input
첫 번 째 줄 의 정수 t 는 데이터 그룹 수 (1 ≤ t ≤ 20) 를 나타 낸다.각 조 의 데 이 터 는 한 줄 에 세 개의 정수 n, a, b (1 ≤ n ≤ 232, n 은 2 의 멱, 1 ≤ a ≤ 109, 1 ≤ b ≤ 109) 를 포함한다.
Output
각 그룹의 데이터 출력 줄 은 정 수 를 포함 하여 정 답 모드 109 + 7 의 나머지 를 표시 합 니 다.
Sample Input
Copy 
1
16 1 1

Sample Output
Copy 
7872

제목: 두 가지 계산 행렬 의 알고리즘 을 정의 합 니 다. 하 나 는 무제 한 n3 차 곱셈 과 (n - 1) n2 차 덧셈 입 니 다. 하 나 는 n% 2 = = 0 시의 18 (n/2) 2 차 덧셈 과 7 차 크기 를 (n/2) 로 계산 합 니 다.×(n/2) 의 곱셈, 입력 한 n 은 2 의 幂 次 이다.최소 결과% 1e9 + 7.
사고: 사고 방향 이 매우 뚜렷 하 다. n 은 첫 번 째 알고리즘 에서 직접 구 할 수 있 거나 두 번 째 알고리즘 에 7 배의 n/2 를 더 해서 구 할 수 있다 는 것 을 관찰 했다.그냥 밀어 주 는 거 야.f [n] = min (suanfa 1 (n), suanfa 2 (n) + 7 * f [n/2]). n 이 2 의 幂 次 인 것 을 고려 하여 n 을 1, 2, 4, 8 로 뜯 었 다.n 에 가서 이 배열 을 풀 면 됩 니 다.그러나 보 존 된 수치 가 너무 클 때 (mod 초과) 남 은 숫자 가 오히려 더 클 때 가장 작 을 수 있 습 니 다. 예 를 들 어 1e9 + 20 에서 남 은 결 과 는 17 이 므 로 자바 대수 로 쓰 거나 c++ 로 대 수 를 모 의 할 수 있 습 니 다.최소 값 을 유지 하기 때문이다.
이것 은 c + wa 코드 입 니 다.
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#pragma GCC optimize(2)
const int maxx=1e5+15;
const ll mod=1e9+7;
using namespace std;
ll d[200];
ll jishu(ll a,ll b,ll n)
{
	ll a1,a2,a3,a4,a5;
	a1=(n*n)%mod;
	a2=(b*n)%mod;
	a3=(a1*a2)%mod;
	a4=(a*(n-1))%mod;
	a5=(a4*a1)%mod;
	ll ans1=(a3+a5)%mod;
	ll x=n/2;
	a1=(x*x*18)%mod;
	return ans1;
}
using namespace std;
ll oushu(ll a,ll b,ll n)
{
	ll a1,a2,a3,a4,a5;
	ll x=n/2;
	a1=(x*x*18*a)%mod;
	return a1;
}
int main()
{
	ll i,j,k,t,m,n;	
	ll a,b,ans2;
	ll cnt=0;
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld",&n);
		scanf("%lld%lld",&a,&b);
		if(n==1)
		{
			printf("%lld
",b);
			continue;
		}
		ll p=0;
		while(n%2==0)
		{
			p++;
			n>>=1;
		}
		d[0]=b;
		for(i=1;i<=p;i++)
		{
			d[i]=min(jishu(a,b,pow(2,i)),oushu(a,b,pow(2,i))+7*d[i-1]);
			d[i]%=mod;	
		}
		printf("%lld
",d[p]%mod);
	}
	return 0;
}

이것 은 자바 입 니 다. 큰 숫자 를 잘 못 써 서 번 거 롭 게 썼 습 니 다. 아 쉬 운 대로 보 세 요.

import java.math.*;
import java.util.*;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {

    static BigInteger jishu(BigInteger a,BigInteger b,BigInteger n){ //    
    	BigInteger ans;
    	ans=BigInteger.valueOf(1);
    	BigInteger a1,a2,a3;
    	a1=n.multiply(n); a2=n.multiply(a1); a2=a2.multiply(b);
    	ans=n.subtract(ans);
    	a3=a1.multiply(ans);
    	a3=a3.multiply(a);
    	a2=a2.add(a3);
        return a2;
    }
    static BigInteger oushu(BigInteger a,BigInteger b,BigInteger n){ // n     
    	BigInteger ans,ans18;
    	ans=BigInteger.valueOf(2);
    	ans18=BigInteger.valueOf(18);
    	BigInteger a1,a2;
    	a2=n.divide(ans);
    	a1=a2.multiply(a2); 
    	a1=a1.multiply(ans18);
    	a1=a1.multiply(a);
        return a1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner cin = new Scanner(System.in) ;
        int t;
        t=cin.nextInt();
    	while(t!=0)
    	{
    		BigInteger[] d = new BigInteger[100];
    		t--;
    		BigInteger a,b,n,x,ans1,ans2,ans7,MOD;
    		MOD=BigInteger.valueOf(1000000007);
    		ans7=BigInteger.valueOf(7);
    		n=cin.nextBigInteger();
    		a=cin.nextBigInteger();
    		b=cin.nextBigInteger();
    		if(n.equals(BigInteger.valueOf(1)))
    		{
    			System.out.println(b);   
    		}
    		else 
    		{
	    		d[0]=b;
	    		int i,j;
	    		for(i=1;i<=50;i++) //  1，2，4，8    n
	    		{
	    			long p=1;
	    			for(j=1;j<=i;j++)   
	    			{
	    				p*=2;
	    			}
	    			x=BigInteger.valueOf(p);
	    			ans1=jishu(a,b,x);
	    			ans2=oushu(a,b,x);
	    			d[i]=ans1.min(ans2.add(d[i-1].multiply(ans7))); //      。
	    			if(x.equals(n)) //   n   
	    			{
	    				 break;
	    			}
	    		}
		       System.out.println(d[i].mod(MOD));   
    		}
	    } 
    }
}

Totori's Switching Game
 
 Accepts: 197
 
 Submissions: 1721
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 32768/32768 K (Java/Others)
Problem Description
우 리 는 Shannon 's Switching Game 이 그림 (graph) 에서 하 는 게임 이라는 것 을 알 고 있 습 니 다. 그의 필승 전략 은 그림 의 두 개의 교차 하지 않 는 생 성 트 리 와 관련 이 있 습 니 다.너 는 이 게임 을 이해 할 필요 가 없다.
이 문제 에서 우 리 는 Totori 's Switching Game (가공) 을 고려 합 니 다.그것 의 정 의 는 매우 간단 합 니 다. 하나의 그림 (무 거 운 변 이 있 을 수 있 지만 자체 고리 가 없습니다) 에서 kk 개의 생 성 트 리 가 존재 하고 그들의 변 이 서로 다 르 면 게이머 가 승리 합 니 다. 그렇지 않 으 면 게이머 가 실패 합 니 다.
Input
첫 번 째 줄 의 정수 tt 는 데이터 그룹 수 (1\\le t\\le 201 ≤ t ≤ 20) 를 나타 낸다.
다음 각 조 데이터 의 첫 줄 에는 3 개의 정수 n, m, kn, m, k 가 포함 되 어 있 으 며, 순서대로 그림 의 포인트 변 수 와 문제 면 의 kk (2\\le n\\le 300, 1\le m\\le 300, 1\le k\\le 3002 ≤ n ≤ 300, 1 ≤ m ≤ 300, 1 ≤ k ≤ 300) 를 나타 낸다.
다음 mm 줄 마다 두 개의 서로 다른 정수 a, ba, b 는 그림 에서 aa 와 bb 를 연결 하 는 변 (1\\le a, b\le n1 ≤ a, b ≤ n) 을 나타 낸다.
Output
각 그룹의 데 이 터 를 한 줄 씩 출력 합 니 다.유저 가 승리 하면 "Yes"를 출력 합 니 다. 그렇지 않 으 면 "No"를 출력 합 니 다.
Sample Input 
2
2 2 2
1 2
2 1
3 4 2
1 2
1 2
1 2
2 3

Sample Output 
Yes
No

제목: 그림 에 k 개의 무 겁 지 않 은 생 성 트 리 가 있 는 지 물 어보 세 요.사실 이 문 제 는 매우 훌륭 합 니 다. 마지막 30 분 에 야 봤 습 니 다. 출시 된 후에 현학 와 가 되 었 습 니 다. 그리고 지나 간 선배 들 과 생각 을 교류 한 것 이 맞 고 더 이상 제출 할 수 없습니다.
먼저 트 리 를 만 드 는 개 수 는 각 점 과 같은 도 보다 작 습 니 다.다음 생 성 트 리 는 n - 1 개의 변 이 필요 합 니 다.그래서 무 겁 지 않 은 생 성 트 리 의 수량 = min (도, m/(n - 1) 은 스스로 그림 을 그 려 서 밀어 볼 수 있 습 니 다.다음 코드 는 괜 찮 을 겁 니 다.
#include
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#pragma GCC optimize(2)
const int maxx=1e5+15;
const ll mod=1e9+7;
using namespace std;
mapbiaoji;
ll x[maxx],y[maxx];
int main()
{
	ll i,j,k,t,m,n;	
	ll a,b,ans2;
	ll cnt=0;
	scanf("%lld",&t);
	while(t--)
	{
		biaoji.clear();
		scanf("%lld",&n);
		scanf("%lld%lld",&m,&k);
		ll minl=1000000;
		for(i=1;i<=m;i++)
		{
			scanf("%lld%lld",&x[i],&y[i]);
			biaoji[x[i]]++;
			biaoji[y[i]]++;
		}
		for(i=1;i<=m;i++) 
		{
			minl=min(minl,biaoji[x[i]]);
			minl=min(minl,biaoji[y[i]]);
		}
		m=(int)(m/(n-1));
		minl=min(m,minl);
		if(minl>=k) printf("Yes
");
		else printf("No
");
	}
	return 0;
}

 
[bash] 파일 설명자, 리 셋 및 tee 명령
음성 인식을 테스트하기 위해 Make Block의 CyberPi를 사용한 시각 프로그래밍

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage