原文連結http://www.cnblogs.com/zhouzhendong/p/8397685.html
2018-02-01
$A$
題意概括
你要買$m$斤水果，現在有$n$個超市讓你選擇。
每個超市的水果價格是固定的。第$i$個超市的水果價格用兩個整數$a_i和b_i$來表示。含義是$a_i$元可以買$b_i$斤。
問你買$m$斤水果最少花費多少錢。
題解
直接枚舉超市，判斷最少的花費就可以了。
代碼
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=5005;
int n;
double m,ans=1e100;
int main(){
scanf("%d%lf",&n,&m);
for (int i=1;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
ans=min(ans,m*a/b);
}
printf("%.10lf",ans);
return 0;
}
$B$
題意概括
找第$k$個各個數位之和為 10 的正整數。($k<=10000$)
題解
從1開始暴搜即可。每次把各個數位加起來判斷一下就可以了。實測$k=10000$的時候大約答案為一千萬左右。
代碼
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int k,ans=0;
bool check(int v){
int res=0;
while (v){
res+=v%10,v/=10;
if (res>10)
break;
}
return res==10;
}
int main(){
scanf("%d",&k);
while (k-=check(++ans));
printf("%d",ans);
return 0;
}
$C$
題意概括
給一個$n \times m$的矩陣，裡面'.'表示空，'*'表示有人，問你有多少個不同的$1 \times k$的全空矩陣。
1<=n,m,k<=2000
題解
我們分每行每列分别枚舉，每個字首'.'大于等于k的格子貢獻為1.
然而本題有坑點，不少$hacker$借此大賺一把。
當$k=1$的時候，答案要除以2！！！
代碼
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int N=2005;
int n,m,k;
char g[N][N];
int main(){
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++)
scanf("%s",g[i]+1);
int ans=0;
for (int i=1;i<=n;i++){
int cnt=0;
for (int j=1;j<=m;j++){
if (g[i][j]=='.')
cnt++;
else
cnt=0;
if (cnt>=k)
ans++;
}
}
for (int i=1;i<=m;i++){
int cnt=0;
for (int j=1;j<=n;j++){
if (g[j][i]=='.')
cnt++;
else
cnt=0;
if (cnt>=k)
ans++;
}
}
if (k==1)
ans/=2;
printf("%d",ans);
return 0;
}
$D$
題意概括
有一個有$n$個節點,$m$條邊的有向圖，每一個節點i上面有一個字母$a_i$。
定義一條路徑的價值為經過的所有節點中遇到的出現次數最多的字母的出現次數。
現在問你價值最大的路徑的價值。（如果價值為$\infty$，輸出$-1$）
$ 1 <= n,m <= 300000 , 'a'<= a_i <= 'z' $
題解
首先考慮 $-1$ 的情況。
顯然，隻要有環就是 $-1$，是以這個可以實作判掉。
于是剩下來的就是一個$DAG$了。
那麼顯然，由于字母隻有26個，那麼我們隻需要拓撲排序 + $DP$就可以了。
具體怎麼DP看代碼。
代碼
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int N=300005,M=300005;
struct Gragh{
int cnt,y[M],nxt[M],fst[N];
void clear(){
cnt=0;
memset(fst,0,sizeof fst);
}
void add(int a,int b){
y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;
}
}g;
int n,m,v[N],vis[N];
int in[N],q[N],head,tail,dp[N][26];
char s[N];
bool dfs_round(int x,int mark){
if (vis[x])
return vis[x]==mark&&in[x];
vis[x]=mark;
in[x]=1;
for (int i=g.fst[x];i;i=g.nxt[i])
if (dfs_round(g.y[i],mark))
return 1;
in[x]=0;
return 0;
}
bool round(){
memset(vis,0,sizeof vis);
memset(in,0,sizeof in);
int mark=0;
for (int i=1;i<=n;i++)
if (!vis[i])
if (dfs_round(i,++mark))
return 1;
return 0;
}
int main(){
scanf("%d%d%s",&n,&m,s+1);
for (int i=1;i<=n;i++)
v[i]=s[i]-'a';
g.clear();
for (int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
g.add(a,b);
}
if (round()){
puts("-1");
return 0;
}
memset(dp,0,sizeof dp);
memset(in,0,sizeof in);
for (int i=1;i<=m;i++)
in[g.y[i]]++;
head=tail=0;
for (int i=1;i<=n;i++)
if (!in[i])
q[++tail]=i;
int ans=0;
while (head<tail){
int x=q[++head];
dp[x][v[x]]++;
for (int i=0;i<26;i++)
ans=max(ans,dp[x][i]);
for (int i=g.fst[x];i;i=g.nxt[i]){
int y=g.y[i];
for (int j=0;j<26;j++)
dp[y][j]=max(dp[y][j],dp[x][j]);
if (!--in[y])
q[++tail]=y;
}
}
printf("%d",ans);
return 0;
}
$E$
題意概括
問有多少個n滿足以下條件：
$ 1<=n<=x $
$ n \cdot a^n \equiv b (mod \; p) $
輸入$a b p x$，保證$p$是素數。
2 ≤ p ≤ 106 + 3, 1 ≤ a, b < p, 1 ≤ x ≤ 1012
題解
由于p為素數，根據費馬小定理，$ a^k \equiv a^{k+(p-1)} (mod \; p) $
于是我們可以從$1$ ~ $p-1$枚舉$n \bmod (p-1)$的值。
然後對于一個解$n\;mod\;(p-1) = i$，我們考慮到$a^n \equiv a^i (mod \; p )$, 是以，可以得到$n \equiv \frac{b}{a^i} (mod \; p)$
即$n \equiv b \times inv(a^i) (mod \; p)$
設$ x=i \; mod \; (p-1),\; y=b \times inv(a^i) \; mod \; p$，則有如下兩個方程：
$n \equiv x\;(mod\;(p-1))$
$n \equiv y\;(mod\;p)$
這個講道理有中國剩餘定理(CRT)合并，但是實際上我們隻需要瞎湊就可以了。
湊出來，$n\equiv -(p-1)\times y\; + \; p \times x (mod \; (p(p-1)))$
于是我們得到了關于$n$的一般形式，那麼計算他的貢獻就很輕松了（這個不講了，直接看代碼吧），總共$p-1$種$n$的形式，每個的貢獻相加即答案。
代碼
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int P=1e6+10;
LL a,b,p,x,inv[P];
LL Pow(LL x,LL y){
if (!y)
return 1;
LL xx=Pow(x,y/2);
xx=xx*xx%p;
if (y&1LL)
xx=xx*x%p;
return xx;
}
LL Inv(LL x){
return Pow(x,p-2);
}
int main(){
scanf("%I64d%I64d%I64d%I64d",&a,&b,&p,&x);
for (LL i=1;i<p;i++)
inv[i]=Inv(i);
LL ans=0;
for (LL i=1;i<p;i++){
LL y=b*inv[Pow(a,i)]%p;
// n=y (mod p)
// n=i (mod p-1)
// n=up+y=v(p-1)+i
// n=kp(p-1) - (p-1)*y + p*i
LL mod=p*(p-1),n=(p*i%mod-(p-1)*y%mod+mod-1)%mod+1;
if (n<=x)
ans+=(x-n)/mod+1;
}
printf("%I64d",ans);
return 0;
}
轉載于:https://www.cnblogs.com/zhouzhendong/p/CF-Round460.html
![goalng nil interface淺析持續學習[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)