数学推导  #include<bits/stdc++.h> using namespace std; const int M=4e4+5; typedef long long ll; ll b[M]; ll a[M]; void sove(){ int n; cin>>n; ll sum=0; ll m=(1+n)*n/2; for(int i=1;i<=n;i++){ ll x; cin>>x; b[i]=x; sum+=x; } if(sum%m!=0||sum/m<n){ cout<<"NO"<<'\n'; retu...

如果a<b，那么a/b=0。 交换数组元素的位置不影响结果，所以可以贪心的去做。 一个小的元素一定会带走一个适当大的元素，这样才是最优的，所以k次操作之后，数组在下标n-k之后的元素都是将会被消耗掉的，而消耗者就是n-k之前的元素，而且一定是在n-k之前的大元素来消耗，这样才会保证k次操作后剩余的值最小。 例如： 1 1 2 2 3 3 3 k=3 ，所以被消耗的数对就是（1，3），（2，3），（2，3），这样数组里就只剩下一个1，显然是最优的。 #include <bits/stdc++.h> using namespace std; typedef long long l...

由题意可以知道，数组填充颜色后一定是这样子的rbrbrbrb（红蓝相间的），而可以被d整除的涂成一种颜色，不可以的涂成另一种颜色。所以一定是只有偶数下标数组可以被d整除或只有奇数下标数组可以被d整除，所以分别求出奇数下标和偶数下标的最大公约数（最大公约数目的是为了奇数偶数下标都可以被该公约数整除的概率降到最低），交叉验证即可。 补充 欧几里得算法求最大公约数 ll gcd(ll a,ll b){ ll r=a%b; while(r){ a=b; b=r; r=a%b; } return b; }  可以作为模板 #include<bits/stdc++.h> using names...

字符串Hash模板 #include<bits/stdc++.h> using namespace std; const int M=1e6+5; typedef unsigned long long ull; char s1[M],s2[M]; ull hs[M]; ull b[M]; const ull base=131; ull getHash(int l,int r){ return hs[r]-hs[l-1]*b[r-l+1]; } int main(){ cin>>s1+1; cin>>s2+1; int m=strlen(s1+1); int ...

第一次做交互题，有点懵逼不知道怎么做 交互题大概就是你输出一句提问，机器回答你一句输入。 这个题呢，对于同一对点查询两次，如果答案不一样，那么两个答案的加和一定就是一个环。就是这么简单。 #include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int q; int cnt=0; for(int i=1;i<=25;i++){ cout<<"? 1 "<<i+1<<endl; ll fl1; cin>>fl1; if(fl1==-...

这个题要求最多可以在餐厅待多少天，人数一共就那么几个，而且至少两人一组，那么如果可以分两人一组就尽量两人一组，这样组的总数才会多，然后就是贪心的思想了，最大的带一个他可以带的最小的，如果带不了，就放弃这个人，这样还能留出更多选择的余地。这个操作用尺取法就ok了。 #include<bits/stdc++.h> using namespace std; const int M=1e5+5; typedef long long ll; ll xx[M]; ll yy[M]; ll cha[M]; int main(){ ios::sync_with_stdio(false),cin.t...

说实话，这道题卡的最久的就是一直在由于1s钟这种暴力会不会超时的问题，还是不太自信，这个题既想走的路径短，又想走的步数最多，那就按着字母顺序走呗。 以logic为例 在字母表中的顺序是这样的 c g i l，所以要想从l走到c路径最短且步数最多，就是l->i->g->c，知道这点之后，这道题就容易了。 #include<bits/stdc++.h> using namespace std; const int M=2e5+5; struct node{ int val; int pos; node(int a,int b){ val=a; pos=b; } nod...

区间dp模板题 #include<bits/stdc++.h> using namespace std; int n; const int M=305; const int INF=0x3f3f3f3f; int a[M],sum[M]; int dp[M][M]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=sum[i-1]+a[i]; } for(int len=2;len<=n;len++){ for(int i=1;i<=n-len+1;i++){ int...

这题虽然蛮简单，但是困扰了很久 这是AC代码 #include<iostream> using namespace std; int m, n; const int M = 3005; int mp[M][M]; const int mod = 2333; int dp[M][M]; int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> m >> n; for (int i = 1; i <= m; i++) { for (int j = 1; j <=...

一、思考状态转移方程如何写 1、原问题和子问题： 原问题：一个人可以左右移动去接饼，当游戏结束时，接到的饼的最大价值。 子问题：一个人可以左右移动，当到达某一时刻时，接到的饼的最大价值。 可见子问题的求解方式与原问题相同。 2、使子问题是最优解 显然是比较每一个由相同状态转移来的状态，得到最优解就是子问题的最优解。 3、是否无后效性： 解决后效性的最好方法就是增加维度，能把物体的每一个状态的所有要素表现清楚，这题由于子问题求解只需要人的位置和游戏时间，那么维度就是二，要素是位置和时间。 现在就得到了状态转移方程： sc[i][j]=max(sc[i][j],sc[i+1][j+k]+have[...

一道很有意思的题，但是思考以后就会发现，绝对不会出现一对相邻的字符不相同，因为不相同且相邻的都消掉了，所以就找最多出现次数的那一个字符。 如果最多出现的字符超过了字符总数的一半，那么这个字符串的长度只能是该字符的数量减去其余字符的总数，因为如果要保证最短的话，其余字符都要带走一个该字符。消减完以后的字符串里面一定只剩最多出现的那个字符了 如果出现的字符数小于等于字符总数的一半，那么就直接把字符总数对2取余即可。其余字符每一个都和一个最大出现次数的字符相消。 #include<bits/stdc++.h> using namespace std; int cnt[27]; int m...

一、考虑状态转移方程怎么写： 1、首先考虑子问题是怎么样的，原问题是求把编号为1~ f的花束，随机放进1~v这v个瓶子里面，且需要按照编号顺序放置，每个花瓶只能放一朵花，的最美观方案。 子问题就可以是，把编号为1~ i的花束，随机放进1~j这j个瓶子里面的最美观方案。显然子问题和原问题的求解方法是一样的，子问题假设正确。 2、接着分析后效性，首先构造一个一维dp数组，dp[M]，描述第M朵花放置在第i个花瓶时的最美观方案，当前状态的选择一定会影响后一个状态的决策，这个状态选了一个数值，为了保证得到最美观方案，下一个状态还需要讨论选哪个数值更好，很复杂，不符合动态规划的本意。 消除后效性 增加一...