C++学习笔记1

A. 求出那个数

题目描述

求出一个最小的正整数 x x x，使得 x x x 每位数字的和恰好为 n n n。

输入格式

第一行一个正整数 T T T，代表测试数据的组数。

接下来 T T T 行每行一个正整数 n n n。

• 1 ≤ T ≤ 1000 1\le T\le1000 1≤T≤1000
• 0 ≤ n 0) n -= 9,s += '9'; cout int TTT; cin TTT; // TTT = 1; while (TTT--) solve(); return 0; } return a b;} void solve() { int n,m,ans = 0; cin >> n >> m; for (int i = 1;i > a[i]; for (int i = 1;i > b[i]; sort(a+1,a+n+1,cmp); sort(b+1,b+n+1); for (int i = 1,j = m;i int TTT; cin TTT; // TTT = 1; while (TTT--) solve(); return 0; } int a,b;}a[100010]; bool cmp(int a,int b) {return a b;} bool check(int x) //训练 x 天 { vector now; //存储训练后马匹的速度 for (int i = 1;i = m; } void bs(int l,int r) { int ans; while (l int mid = (l+r)/2; if (check(mid)) ans = mid,r = mid-1; else l = mid+1; } cout cin n > m; for (int i = 1;i > a[i].a >> a[i].b; for (int i = 1;i > b[i]; sort(b+1,b+n+1,cmp); int l = 0,r = 1e14; if (!check(r)) cout int TTT; cin > TTT; // TTT = 1; while (TTT--) solve(); return 0; }

  D. 放置方案数

  现在有 k k k 种颜色的小球，每一种颜色的小球有若干个，有 n n n 个盒子排成一排，现在要往盒子里放球，每一个盒子需要放 1 1 1 个小球，要求相邻的盒子之间最多只有 2 2 2 个连续颜色相同的小球，问你有多少种方案，由于答案很大，请你对 1 0 9 + 7 10^9+7 109+7 取模。

  输入格式

  第一行输入一个整数 T T T，代表有 T T T 组测试数据。

  接下来 T T T 行，每行给出两个正整数 n , k n,k n,k，含义如题。

  • 1 ≤ T ≤ 1 0 3 1\le T\le10^3 1≤T≤103
  • 1 ≤ n , k ≤ 1 0 5 1\le n,k\le10^5 1≤n,k≤105

    输出格式

    对于每组测试数据，在一行中输出答案。

    样例

    输入 #1

    2
    1 1
    3 2
    

    输出 #1

    1
    6
    

    1. 最多可以有连续两个盒子放相同颜色的球，所以只需要考虑连续的三个盒子即可；
    2. 用 d p i 0 dp_{i_0} dpi0​​ 表示第 i i i 个盒子放和第 i − 1 i−1 i−1 个盒子球颜色不同的球的方案数；
    3. 用 d p i 1 dp_{i_1} dpi1​​ 表示第 i i i 个盒子放和第 i − 1 i−1 i−1 个盒子球颜色相同的球的方案数；
    4. d p i 0 = ( d p i − 1 0 + d p i − 1 1 ) × ( k − 1 )   %   ( 1 0 9 + 7 ) dp_{i_0}=(dp_{{i-1}_0}+dp_{{i-1}_1})\times(k-1)\ \%\ (10^9+7) dpi0​​=(dpi−10​​+dpi−11​​)×(k−1) % (109+7)；
    5. d p i 1 = d p i − 1 0 dp_{i_1}=dp_{{i-1}_0} dpi1​​=dpi−10​​。
    6. 最终的答案取 ( d p n 0 + d p n 1 )   %   m o d (dp_{n_0}+dp_{n_1})\ \%\ mod (dpn0​​+dpn1​​) % mod。

       十年 OI 一场空，不开 long long 见祖宗！

    #include 
    #define int long long
    using namespace std;
    const int mod = 1000000007;
    int dp[100010][2];
    void solve()
    {
    	int n,m;
    	cin >> n >> m;
    	dp[1][0] = m;
    	dp[1][1] = 0;
    	for (int i = 2;i 
    		dp[i][0] = (dp[i-1][0]+dp[i-1][1]) * (m-1) % mod;
    		dp[i][1] = dp[i-1][0];
    	}
    	cout 
    	int TTT;
    	cin  TTT;
    //	TTT = 1;
    	while (TTT--) solve();
    	return 0;
    }
    

    h2E. 密码破解/h2 p密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律，常应用于编制密码以保守通信秘密的。从古代传递情报道现在电脑的通信一直扮演着一个十分重要的角色。相信你一定听说过「凯撒密码」，它属于是一种替换密码。一种凯撒密码的替换方式是 A → D , B → E , C → F , … , X → A , Y → B , Z → A A\to D,B\to E,C\to F,\dots,X\to A,Y\to B,Z\to A A→D,B→E,C→F,…,X→A,Y→B,Z→A。以数学的方式来说，我们让 A = 0 , B = 1 , C = 2 , … , Z = 25 A=0,B=1,C=2,\dots,Z=25 A=0,B=1,C=2,…,Z=25，使用密钥 x x x 加密明文 a a a 得到的密文就是 ：/p p E x ( a ) = ( a + x ) mod ⁡ 26 E_x(a)=(a+x) \operatorname{mod} 26 Ex​(a)=(a+x)mod26/p p以现在的计算机技术，凯撒密码是很容易破解的，即使我们不知道其中用来加密的密钥 x x x 的值，我们依然可以借助计算机强大的算力通过频率分析方法将其暴力解出。当密文长度足够大的情况下，可以先分析密文中每个字母出现的频率，然后将这一频率与正常情况下的该语言字母表中所有字母的出现频率做比较。例如在英语中，正常明文中字母 E E E 和 T T T 出现的频率特别高，而字母 Q Q Q 和 Z Z Z 出现的频率特别低，而在法语中出现频率最高的字母是 E E E，最低的是 K K K 和 W W W。可以通过这一特点，分析密文字母出现的频率，可以估计出正确的密钥 x x x。/p p这里我们要介绍一种改良版的凯撒密码。现在你有一组密钥 x 1 , x 2 , x 3 , … , x l x_1,x_2,x_3,\dots,x_l x1​,x2​,x3​,…,xl​，要加密的信息 a 1 , a 2 , a 3 , … , a n a_1,a_2,a_3,\dots,a_n a1​,a2​,a3​,…,an​ 得到密文 c 1 , c 2 , c 3 , … , c n c_1,c_2,c_3,\dots,c_n c1​,c2​,c3​,…,cn​。我们拿第一个密钥的字母 x 1 x_1 x1​ 加密 a 1 a_1 a1​，拿第二个密钥的字母 x 2 x_2 x2​ 加密 a 2 a_2 a2​， … \dots …。如果密钥用完了，我们就拿前面得到的密文来用，也就是拿 c 1 c_1 c1​ 来加密 a l + 1 a_{l+1} al+1​。/p p c i = { a i + x i mod ⁡ 26 i ≤ l a i + c i − l mod ⁡ 26 i > l c_i = \begin{cases} a_i+x_i \operatorname{mod} 26 & i \le l \\ a_i+c_{i-l} \operatorname{mod} 26 & i>l \end{cases} ci​={ai​+xi​mod26ai​+ci−l​mod26​i≤li>l​

    现在，给你几组用同样的密钥加密的明文密文配对，请你写程序来破解出密钥。

    输入格式

    第一行一个正整数 T T T，代表测试数据的组数。

    每组测试数据在第一行给出一个正整数 N N N，代表有几对明文密文配对。

    接下来 N N N 行每行给出两个以空格分隔且只由大写字母组成的字符串 s 1 , s 2 s_1,s_2 s1​,s2​​，前面的代表明文，后面的是加密后的密文。

    • 1 ≤ T ≤ 200 1\le T\le200 1≤T≤200
    • 1 ≤ N ≤ 10 1\le N\le10 1≤N≤10
    • 1 ≤ ∣ s 1 ∣ = ∣ s 2 ∣ ≤ 300 1\le\lvert s_1\rvert=\lvert s_2\rvert\le300 1≤∣s1​∣=∣s2​∣≤300

      输出格式

      对于每组输入在一行中输出一个字符串，代表能够将 N N N 组明文分别加密成对应密文的密钥。

      如果有多种可能的密钥，请输出最短的那个。

      如果没有任何符合的密钥，请输出 -。

      样例

      输入 #1

      2
      1
      VAMRI VCYMK
      2
      CAKES DEOHW
      CAKES DEOHW
      

      输出 #1

      ACM
      BEE
      

      #include 
      #define int long long
      using namespace std;
      const int N = 20;
      int n;
      string s1[N],s2[N];
      bool check(string str,string ming,string mi)
      {
      	//ming -> 明文
      	//mi -> 密文
      	string s = "";
      	for (int i = 0;i > n;
      	for (int i = 0;i > s1[i] >> s2[i];
      		for (int j = 0;j