2020 지산 의 길 재 경기

숫자.
총 5 개의 테스트 포인트 가 테스트 포인트 당 20 점 입 니 다.
각 테스트 지점 마다 1 초 동안 메모리 상한 선 512 MB 를 실행 합 니 다.

        a,b ，     a     （        a   aa ），     a   b    a≡0(mod b)，  a   b    。
                a。
  ： a      0 。

입력 형식

      ，   a   b 。

출력 형식

      ，            a 。
       

    20%    ，   b=1。

    40%    ，   b≤2。

   100%    ，   0≤a≤10^14,0<b≤10^180.

샘플 입력

0 1

샘플 출력

900

예 를 들 어 해석 하 다.

       1    ，  a       100−999               。

사고의 방향

   ，    ac ，   a   ， pow     100-999   ，      

#include
#include
#include
#include
using namespace std;
#define IO ios::sync_with_stdio(0); cin.tie(0);//  
int main()
{
	IO;
	long long a,b;
	cin>>a>>b;
	long long len=0,k=a,ans=0;//  oi   ，  longlong   
	while(k)
	{
		k/=10;
		len++;
	}
	for(int i=100;i<=999;i++)
	{
		long long j=i*pow(10,len);//        ，      
		if((j+a)%b==0)ans++;
	 } 
	 cout<<ans<<endl;
    return 0;
}

격자
총 5 개의 테스트 포인트 가 테스트 포인트 당 20 점 입 니 다.
각 테스트 지점 마다 1 초 동안 메모리 상한 선 512 MB 를 실행 합 니 다.

    n∗n    ，     (0,0)     (n,n) 。

             ，      ：
          (a,b) ，      w1       (a,b+1)   (a+1,b) 。
      (a,b)        ，        1 ，        w2       (a+1,b+1) 。

                         ，     。

입력 형식

        n,k,w1,w2 。

    k  ，  i       xi,yi ，    i         。

출력 형식

      ，              。
       

   20%    ，   n≤3 。

    20%    ，           (0,0)   (n,n)      ，         i∈[1,k] ， xi=yi​ 。

   100%    ，   1≤n,w1,w2≤109,0≤k≤2000,0≤xi,yi<n1 ，          。

샘플 입력

3 2 132 100
0 1
1 2

샘플 출력

464

예 를 들 어 해석 하 다.

             ：
(0,0)→(0,1)→(1,2)→(2,3)→(3,3)

  (0,1),(1,2)    2 （   100   ） ，        1 （   132   ）。

생각:

          ...    ，        

  1   ，   w1。  2   ，   w2。
       1，  (x,y)    (x+y)∗w1

(x+y)∗w1。

        2，                ，          ，                    ，       。     ：

  f[i]
f[i]    ii        ，  
num=a[i].x+a[i].y−a[j].x−a[j].y−2num=a[i].x+a[i].y−a[j].x−a[j].y−2
f[i]=min(f[i],f[j]+num∗w1+w2)f[i]=min(f[i],f[j]+num∗w1+w2)

코드:

#include
#include
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 2005;
ll f[maxn];
struct Node //    
{
    int x,y;
}a[maxn];

int cmp(Node a,Node b) {//      
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
int main()
{
    int n,k,w1,w2;
	scanf("%d%d%d%d",&n,&k,&w1,&w2);
    for(int i = 1;i <= k;i++) 
	{
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    sort(a + 1,a + 1 + k,cmp);//         
    a[k + 1].x = n;
	a[k + 1].y = n;
    k++;
    for(int i = 1;i <= k;i++) 
	{
        f[i] = 1ll * w1 * (a[i].x + a[i].y);
    }
    
    for(int i = 2;i <= k;i++)
	 {
        for(int j = 1;j < i;j++)
		 {
            if(a[j].x < a[i].x && a[j].y < a[i].y) 
			{
                int num = a[i].x + a[i].y - a[j].x - a[j].y - 2;
                f[i] = min(f[i],f[j] + 1ll * num * w1 + w2);
            }
        }
    }
    
    printf("%lld
",f[k]);
    return 0;
}

유향 무 환 도
총 5 개의 테스트 포인트 가 테스트 포인트 당 20 점 입 니 다.
각 테스트 지점 마다 1 초 동안 메모리 상한 선 512 MB 를 실행 합 니 다.

   k ，                 （    1-n ），    1   n         k 。

입력 형식

        k,N，                    （             N ）。
    

         n,m，             。

    m  ，        u,v ，       u   v     。

          ，      。

데이터 범위 와 약속

     	N	k
1	=2	=1
2	=4	=3
3 =10^3	≤500
4−5 =66  <2^64

   100%    ，   0<k<2^64 。

       ，         1≤m≤10^5  n>1 。

  ：           、           ，                     。
    

2 1000

샘플 출력

3 3
1 2
2 3
1 3

예 를 들 어 해석 하 다.
두 경 로 는 다음 과 같 습 니 다.

1→2→3
1→3

코드:

#pragma GCC optimize(2)

#include
#include
#include 
#include 
#include
#include 

using namespace std;

typedef unsigned long long ll;

vector<pair<int,int> >vec;

int main() {
    ll n,k;scanf("%llu%llu",&k,&n);
    
    ll tmp = k;
    int cnt = 0;
    while(tmp) {
        cnt++;
        tmp /= 2;
    }
    
    if(n == 2 && k == 1) {
        printf("2 1
");
        printf("1 2
");
        return 0;
    } else if(n == 4 && k == 3) {
        printf("4 5
");
        printf("1 2
2 3
3 4
1 3
2 4
");
        return 0;
    }
    
    int N = cnt + 2;
    for(int i = 2;i <= cnt + 1;i++) {
        for(int j = i + 1;j <= cnt + 2;j++) {
            vec.push_back({i,j});
        }
    }
    
    for(int i = 0;i < cnt;i++) {
        if((k >> i) & 1) {
            int nex = cnt - i + 1;
            vec.push_back({1,nex});
        }
    }
    
    printf("%d %d
",N,(int)vec.size());
    for(int i = 0;i < vec.size();i++) {
        printf("%d %d
",vec[i].first,vec[i].second);
    }
    return 0;
}