#include<bits/stdc++.h>
using namespace std;
int n,a,b,c;
int main()
{
cin>>a>>b;
c=a+b;
if(c>=15&&b>=8) cout<<1<<endl;
else if(c>=10&&b>=3) cout<<2<<endl;
else if(c>=3) cout<<3<<endl;
else cout<<4<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n;
int a[N], b[N];
int main()
{
scanf("%d", &n);
int res = INF;
for(int i = 1; i <= n; ++ i)
{
scanf("%d%d", &a[i], &b[i]);
res = min(res, a[i] + b[i]);
}
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
if(i != j) res = min(max(a[i], b[j]), res);
printf("%d\n", res);
return 0;
}
我们知道\((a-b)^2\)可以转化为\(a^2+b^2-2ab\),我们知道，对于每个\(a_i\)，都需要计算\((n-1)\)次。
所以，我们先通过递推求出\((n-1)a_i^2\)的值和，然后计算后面\(-2ab\).
对于每一个\(a_i\),都在式子中出现了\((n-1)\)次，我们需要一个数组去算\(A\)数组的前缀和，然后在\(O(n)\)的时间里就通过。
代码：
#include<bits/stdc++.h>
using namespace std;
long long n;****
const int N=3e5+5;
long long sum[N],a[N];
long long ans=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
ans=ans+((n-1)*a[i]*a[i]);
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++){
ans=ans-(2*a[i]*(sum[n]-sum[i]));
}
cout<<ans<<endl;
system("pause");
return 0;
}
我们假设现在已经有\(S\)个节点被访问过了，那么下一次能使\(|S|\)增加的概率是\(\dfrac{N - |S|}{N}\)。
这样的概率符合几何分布，已知几何分布的期望公式为\(\dfrac{1}{p}\),其中，\(p\)为概率。
那么当前状态的期望就是：\(\dfrac{N}{N-|S|}\)。
初始状态，\(|S|=1\),结束时，\(|S|=N\),因此，我们最终的期望公式就是：\(\sum\limits_{i = 1}^{n - 1}\dfrac{N}{N - i}\)
代码：
#include<bits/stdc++.h>
using namespace std;
double n;
double ans;
int main()
{
cin>>n;
for(int i=1;i<n;i++){
ans=ans+n/(n-i);
}
printf("%.10f\n",ans);
system("pause");
return 0;
}
我们可以把这种题看成一个队列。用一个\(last\)数组去记录上一个相同的数出现的位置，如果两个相同的数的距离大于\(m\),那么它就可以当成是答案。
最后，我们因为有些数其实压根没有在那个序列中出现。因此，我们要从\(0——n\) 遍历一遍，看看是否可以被选成是答案。
能被选成答案的要求是
\(n+1-last[i]>m\),也就是到结尾的距离比m大。(如果last=0的话，序列中没有出现，也可以选择上，其实是多一种考虑)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,m;
int last[N],ans=0x3f3f3f3f;
int main()
{
cin>>n>>m;
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
if(i-last[x]>m) ans=min(x,ans);
last[x]=i;
}
for(int i=0;i<=n;i++)
if(n+1-last[i]>m)//处理边界情况
ans=min(ans,i);
cout<<ans<<endl;
system("pause");
return 0;
}
这里是参考了这位大神的题解（因为完全没有任何思路）
令 \(f[i][j]\) 为前\(i\) 位选了 \(j\) 种的方案数，且选出的方案都严格小于上界
当上一位未达到上界时：
\(f[i+1][j]+=f[i][j]?j\)
\(f[i+1][j+1]+=f[i][j]?(16?j)\)
因为要处理前导零，所以从 \(0\) 转移要特殊处理：
\(f[i+1][1]+=f[i][0]?15\)
\(f[i+1][0]+=f[i][0]\)
再统计上一位达到上界时，当前位取 \(0 ~ v[i]?1\) 的贡献
最后特判掉所有位都取到上界是否符合题意
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int P = 1e9 + 7;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int N = 3e6 + 10;
int main()
{
int n;
string str;
vector<int> v;
cin >> str >> n;
for(auto x : str)
if(x >= ‘0‘ && x <= ‘9‘) v.push_back((int)(x - ‘0‘));
else v.push_back((int)(10 + x - ‘A‘));
vector<vector<int> > f(str.size() + 1, vector<int>(18, 0));
int state = 0;
for(int i = 0; i < (int)str.size(); ++ i)
{
for(int j = 1; j <= 16; ++ j)
{
f[i + 1][j] = (f[i + 1][j] + (LL)f[i][j] * j % P) % P;
f[i + 1][j + 1] = (f[i + 1][j + 1] + (LL)f[i][j] * (16 - j) % P) % P;
}
f[i + 1][1] = (f[i + 1][1] + (LL)f[i][0] * 15 % P) % P;
f[i + 1][0] = (f[i + 1][0] + f[i][0]) % P;
for(int j = 0; j < v[i]; ++ j)
{
int nstate = state;
if(i || j) nstate |= (1 << j);
f[i + 1][__builtin_popcount(nstate)] += 1;
}
state |= (1 << v[i]);
}
int res = f[str.size()][n] + (__builtin_popcount(state) == n);//这个意思是计算二进制中有多少个一
cout << res << endl;
return 0;
}
结束！
原文：https://www.cnblogs.com/guanlexiangfan/p/14499094.html