周赛题目证明+at数学题

题目链接：https://www.acwing.com/problem/content/4795/

比赛的时候感觉插入到最后面是最大的，当时只是感觉并没严格证明，y总说比赛的时候可以不用严格证明，赛后要这样做，这样碰到类似的题可以增加作对的几率

分析：

总价值的最大取决于插入的位置i和该位置权值的大小w[i]，那我们就要明确保证最大的策略

1.插入的w[i]必须是最大的

2.插入的位置要么是中间要么是末尾

那是中间还是末尾呢？

这就需要证明一下，假设插入的是中间，那他下一个位置的权值设为w'[i]，对他们价值做差i*w_max-(i+1)*w'[i]<=0；

不断把w_max的位置挪后会发现这样的价值是大于在中间的价值的

所以贪心策略就明确了：1.插入的w[i]必须是最大的

2.插入的位置是末尾

AC代码:

 1 /*#include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     string s;
 7     int k;
 8     vector<int> w(26);
 9     cin >> s;
10     cin >> k;
11     for(int i = 0; i < 26; i++)
12         cin >> w[i];
13 
14     int n = s.size();
15     int sum = 0;
16     for(int i = 0; i < n; i++)
17         sum += (i + 1) * w[s[i] - 'a'];
18 
19     int result = sum;
20     for(int i = 0; i < k; i++)
21         result += (n + i + 1) * (*max_element(w.begin(), w.end()));
22 
23     cout << result;
24     return 0;
25 }*/
26 //比赛的时候感觉是往最后面插是最优贪心策略，但没证明，y总说贪心题要考后证明一下才能保证自己以后作对这种题的几率
27 //首先构成最大价值的是由w[i]与i决定的，那第一点肯定是要确保w[i]是最大的
28 //第二点就是关于往哪插入的问题，假设我们往中间插入，设他下一个位置的价值是w[i]',对他们w[i]*i做差可得
29 //i*w_max[i]-（i+1)*w[i]'<=0
30 //也就是说我们不断的将w_max的位置后移所得到的最终价值（移动到最后的位置）是肯定大于其他位置的
31 //那最优的贪心策略就是将他往后插入
32 //证毕
33 #include<bits/stdc++.h>
34 using namespace std;
35 #define int long long 
36 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
37 string s;
38 int max_w;
39 int res;
40 int w[26];
41 int k;
42 signed main()
43 {
44     IOS;
45     cin>>s;
46     cin>>k;
47     for(int i=0;i<26;i++)
48     {
49         cin>>w[i];
50         max_w=max(max_w,w[i]);
51     }
52     for(int i=0;i<s.length();i++)
53     {
54         res+=w[s[i]-'a']*(i+1);
55     }
56     for(int i=s.length();i<s.length()+k;i++)
57     {
58         res+=max_w*(i+1);
59     }
60     cout<<res<<endl;
61     return 0;
62 }
63 
64 作者：江上舟摇
65 链接：https://www.acwing.com/activity/content/code/content/5145994/
66 来源：AcWing
67 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

AT:https://atcoder.jp/contests/abc284/tasks/abc284_d

这道题是这样的，给定一个整数N，N可以被分解为p^2*q，q,p都是素数，求出q,p

分析：

1. n的最大范围是9e18，假设qp相等的情况下，min(p,q)是肯定要小于N的开三次方根
2. 那么只要在[2,N的开三次方根]内找出满足p^2*q==n的质数就能解决这个问题
3. AC代码：

4.  1 //昨天没做出来，难受
    2 //其实分析一下我昨天的代码应该是忘了break了，为此我特地做了实验，在AC代码的基础上如果不加break就会超，也难怪，比较
    3 //数据太大啦
    4 //分析
    5 //n的最大范围是9e18，假设qp相等的情况下，min(p,q)是肯定要小于N的开三次方根的
    6 //那么只要在[2,N的开三次方根]内找出满足p^2*q==n的质数就能解决这个问题
    7 //不要忘记找到之后终止循环
    8 #include<bits/stdc++.h>
    9 using namespace std;
   10 #define int long long
   11 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   12 int t;
   13 int n;
   14 inline int read(){
   15      int s=0,w=1;char ch=getchar();
   16     while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
   17     while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
   18     return s*w;
   19 }
   20 signed main()
   21 {
   22     IOS;
   23     t=read();
   24     while(t--)
   25     {
   26         int p=0;
   27         int q=0;
   28         n=read();
   29         //for(int i=2;i*i*i<=n;i++)
   30         for(int i=2;i<=3e6;i++)
   31         {
   32             if(n%i!=0)
   33             continue;
   34                 if((n/i)%i==0)
   35                 {
   36                     p=i;
   37                     q=n/i/i;
   38                     break;
   39                 }
   40                 else
   41                 {
   42                     q=i;
   43                     p=round(sqrt(n/i));
   44                     break;
   45                 }
   46         }
   47         cout<<p<<" "<<q<<endl;
   48     }
   49     return 0;
   50 }