- Prob.1 生活大爆炸版 石头剪刀布
模拟。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int mp[5][5]={{0,0,1,1,0},
{1,0,0,1,0},
{0,1,0,0,1},
{0,0,1,0,1},
{1,1,0,0,0}};
int A[205],B[205];
int n,lA,lB,ansA,ansB;
int main(){
scanf("%d%d%d",&n,&lA,&lB);
for(int i=1;i<=lA;i++) scanf("%d",&A[i]);
for(int i=1;i<=lB;i++) scanf("%d",&B[i]);
for(int i=1,pA=0,pB=0;i<=n;i++) {
pA++; if(pA>lA) pA=1;
pB++; if(pB>lB) pB=1;
ansA+=mp[A[pA]][B[pB]];
ansB+=mp[B[pB]][A[pA]];
}
printf("%d %d",ansA,ansB);
return 0;
}
- Prob.2 联合权值
可以叫树形dp吧。
每次考虑把当前子树的根作为长度为2的路径的一个端点或中转点。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 200005
using namespace std;
const int mod=10007;
struct edge{
int to,next;
}e[MAXN*2];
int w[MAXN],head[MAXN];
int sm[MAXN],mx[MAXN];
int n,ent=2,ansx,anss;
void add(int u,int v){
e[ent]=(edge){v,head[u]};
head[u]=ent++;
}
void dfs(int u,int fa){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
anss=(1ll*anss+1ll*sm[v]*w[u]*2)%mod;
anss=(1ll*anss+1ll*sm[u]*w[v]*2)%mod;
sm[u]+=w[v];
ansx=max(ansx,mx[v]*w[u]);
ansx=max(ansx,mx[u]*w[v]);
mx[u]=max(mx[u],w[v]);
}
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
dfs(1,0);
printf("%d %d",ansx,anss);
return 0;
}
- Prob.3 飞扬的小鸟
dp+转移优化
首先 70%的很好想：
dp[i][j]表示到达(i，j)的最小点击次数，显然没有后效性。
┌dp[i-1][j+y[i-1]] (不点击)
dp[i][j]=min│
┕dp[i-1][j-k*x[i-1]]+k(点击)
这个方程的复杂度为 (n*m*m)
考虑优化，发现这样一个东西：
只考虑"点击"这一个转移来源的话，那么
dp[i][j]只比dp[i][j-x[i-1]]多了一个转移来源。
然后就是一个前缀的思想了，即我们把第二维的j从小到大枚举
那么(这里在说"点击"这一个来源)
dp[i][j]=min(dp[i-1][j-x[i-1]],dp[i][j-x[i-1])+1
这样就把"点击"时的O(n)转移优化为了O(1)。
注意j==m时要特殊处理。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;
int x[10005],y[10005],l[10005],h[10005],fg[10005];
int dp[10005][1005];
int n,m,k,ans=INF;
bool legal(int i,int j){
if(j<=0||j>m) return 0;
if(!fg[i]) return 1;
return l[i]<j&&j<h[i];
}
void cmin(int &a,int b){
if(a>b) a=b;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]);
for(int i=1,p;i<=k;i++) scanf("%d",&p),fg[p]=1,scanf("%d%d",&l[p],&h[p]);
for(int j=l[0]+1;j<(fg[0]?h[0]:m+1);j++) dp[0][j]=0;
for(int i=1;i<=n;i++){
//click
for(int j=0;j<m;j++){
int a=legal(i-1,j-x[i-1])?dp[i-1][j-x[i-1]]:INF;
int b=j>x[i-1]?dp[i][j-x[i-1]]:INF;
cmin(dp[i][j],min(a,b)+1);
}
for(int j=m;j>=0;j--){
int a=legal(i-1,j)?dp[i-1][j]:INF;
cmin(dp[i][m],a+max(m-j-1,0)/x[i-1]+1);
}
//no-click
for(int j=0;j<=m;j++){
int a=legal(i-1,j+y[i-1])?dp[i-1][j+y[i-1]]:INF;
cmin(dp[i][j],a);
}
}
for(int i=n;i>=0;i--){
for(int j=1;j<=m;j++){
if(i==n) cmin(ans,dp[i][j]);
if(i!=n&&legal(i,j)&&dp[i][j]<INF){
printf("%d\n%d",0,k);
return 0;
}
}
if(ans<INF) break;
if(fg[i]) k--;
}
printf("%d\n%d",1,ans);
return 0;
}
- Prob.4 无线网络发射器选址
二维前缀和，求子矩阵和。
千万不要枚举多了。否则会多统计。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int sum[150][150];
int d,n,ans,cnt;
int area(int x1,int y1,int x2,int y2){
return sum[x2][y2]-sum[x1][y2]-sum[x2][y1]+sum[x1][y1];
}
int main(){
scanf("%d%d",&d,&n);
for(int i=1,x,y,k;i<=n;i++){
scanf("%d%d%d",&x,&y,&k);
x++;y++;
sum[x][y]+=k;
}
for(int i=1;i<=129;i++)
for(int j=1;j<=129;j++)
sum[i][j]=sum[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
for(int i=1,x1,y1,x2,y2,now;i<=129;i++)
for(int j=1;j<=129;j++){
x1=max(i-d-1,0); y1=max(j-d-1,0);
x2=min(i+d,129); y2=min(j+d,129);
now=area(x1,y1,x2,y2);
if(now>ans) ans=now,cnt=0;
if(now==ans) cnt++;
}
printf("%d %d",cnt,ans);
return 0;
}
- Prob.5 寻找道路
反向BFS给无法到终点的点打上标记，
然后再给那些存在一条出边无法到终点的点打上标记。
最后对没有标记的点跑最短路。（因为边权为1，BFS即可）
代码：
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct edge{
int to,next;
}e1[200005],e2[200005];
int head1[10005],head2[10005],vis[10005],dis[10005];
int n,m,ent1=2,ent2=2,S,T;
void add(int u,int v,int &ent,int *head,edge *e){
e[ent]=(edge){v,head[u]};
head[u]=ent++;
}
void BFS1(){
queue<int> q;
vis[T]=1; q.push(T);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head2[u];i;i=e2[i].next){
int v=e2[i].to;
if(vis[v]) continue;
vis[v]=1; q.push(v);
}
}
for(int u=1;u<=n;u++) if(!vis[u])
for(int i=head2[u];i;i=e2[i].next){
int v=e2[i].to;
if(!vis[v]) continue;
vis[v]=-1;
}
}
void BFS2(){
queue<int>q; q.push(S); dis[S]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head1[u];i;i=e1[i].next){
int v=e1[i].to;
if(dis[v]||vis[v]!=1) continue;
dis[v]=dis[u]+1;
q.push(v);
}
}
if(dis[T]==0) printf("-1");
else printf("%d",dis[T]-1);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++)
scanf("%d%d",&u,&v),
add(u,v,ent1,head1,e1),
add(v,u,ent2,head2,e2);
scanf("%d%d",&S,&T);
BFS1();
BFS2();
return 0;
}
- Prob.6 解方程
又是一大神题，车大佬给我讲了好久才明白。
首先按照题目的意思，我们找出x，要使得：
A0 + A1*X1 + A2*X2 + A3*X3 + ...... + An*Xn == 0 [1]
但是无奈 A的范围很大，无法直接计算。
（然后就阴差阳错的考虑到取模上去）
对等式两边同时取模 M(先只对系数取模)
那么得到：（Bi = Ai % M）
B0 + B1*X1 + B2*X2 + B3*X3 + ...... + Bn*Xn == 0 [2]
然后动动脑子，可以发现满足 [1]式的x 则是一定满足 [2]式的x。
！！！
那么我们是不是可以把原来的 [1]式 通过取模后得到系数较小的 [2]式，
然后通过 可以计算的[2]式来找合法的x。
好吧，显然有错。
虽然满足 [1]式的x 一定是满足 [2]式的x，
但是满足 [2]式的x 却不一定是满足[1]式的x。（这个好理解吧）
显然满足 [2]式的x，带入[1]式左边，可能得到两个值，一个是0（合法），一个是k * M（非法）
那怎么办？ 接下来就神奇了。
我们多选几个 M(5-6个) : M1 , M2 , M3 ,M4 , M5（M尽量为大素数或某些大素数的乘积）
那么对于一个x，在这5种M取模下，如果都满足 [2]式（即其值==0），那么这个x就非常可能是满足 [1]式的，直接把它当做答案。
为什么呢。
如果都满足，那么把这个 x 带入 [1]式后，得到的值要么为 0（合法），要么为 k * M1M2M3M4M5（非法）。
（对于非法的 x，就是带入 [1]式后，其值==k * M1M2M3M4M5，即是"我们选取的这几个模值的乘积的倍数"。）
而对于所有的x，带入 [1]式后，最多产生 10^6个值。
那么在出题人不知道我们选取的模值的情况下，要使得某个x带入 [1]式后恰好等于"我们选取的模数的乘积的倍数"的几率是很小的。
所以，除非运气不好，否则我们选的几个M （强调：M尽量为大素数或某些大素数的乘积），就可以达到筛选出正确的x的目的。
#include<cctype>
#include<cstdio>
#include<cstring>
#include<iostream>
#define _ %mod[j]
using namespace std;
const int mod[6]={13923, 16851, 24989, 19997, 11987, 13999};
int val[1000005][6]/*mod意义下*/,A[105][6],ANS[1000005];
int n,m,cnt;
void readai(){
int fu;char ch; ch=getchar();
for(int i=0;i<=n;i++){
fu=1;
while(!isdigit(ch)){
if(ch=='-') fu=-1;
ch=getchar();
}
while(isdigit(ch)){
for(int j=0;j<=5;j++)
A[i][j]=(A[i][j]*10+(ch-'0'))_;
ch=getchar();
}
for(int j=0;j<=5;j++) A[i][j]*=fu;
}
}
int Pow(int a,int b,int j){
int now=1;
while(b){
if(b&1) now=(1ll*now*a)_;
a=(1ll*a*a)_;
b>>=1;
}
return now;
}
int cal(int x,int j){
int ans=0;
for(int i=0;i<=n;i++)
ans=(ans+(1ll*A[i][j]*Pow(x,i,j))_)_;
return ans;
}
int main(){
scanf("%d%d",&n,&m);
readai();
for(int j=0;j<=5;j++)
for(int i=1;i<mod[j];i++)
val[i][j]=cal(i,j);
for(int i=1;i<=m;i++){
bool fg=1;
for(int j=0;j<=5;j++)
if(val[(i)_][j]) fg=0;
if(fg) ANS[++cnt]=i;
}
printf("%d\n",cnt);
for(int i=1;i<cnt;i++) printf("%d\n",ANS[i]);
printf("%d",ANS[cnt]);
return 0;
}