打开博客发现上次咕咕咕了写一半。。想想还是补完，顺便复习下。
A、胖胖的牛牛
好像bfs也行。我这里用的是dfs，后来用了最短路解。
这里主要说最短路。将每个点分成上下左右四个点，用点，其中i、j是点坐标，k为其方向：0为左，1为上，2为右，3为下，(因为当i=n,j=n时，
，所以是
)然后用0点作为超级起点,
作为超级终点，套下最短路就行了。
DFS:
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
template<typename T>void write(T x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
{
write(x / 10);
}
putchar(x % 10 + '0');
}
template<typename T> void read(T& x)
{
x = 0; char ch = getchar(); ll f = 1;
while (!isdigit(ch)) { if (ch == '-')f *= -1; ch = getchar(); }
while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }x *= f;
}
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; };
ll ksm(ll a, ll n) {//看是否要mod
ll ans = 1;
while (n) {
if (n & 1) ans = (ans * a) % mod;
a = a * a % mod;
n >>= 1;
}
return ans % mod;
}
//==============================================================
const int maxn = 1e2 + 10;
int vis[maxn][maxn];
int dir[4][2] = { 1,0,-1,0,0,1,0,-1 };
//上下右左
ll ans = inf;
int xa, xb, ya, yb;
int n;
char mp[maxn][maxn];
void dfs(int x, int y,int pos, ll cnt) {
if(cnt>=ans) return;//剪枝
if(mp[x][y]=='B'){
ans=min(ans,cnt);
return ;
}
rep(i, 0, 3) {
int dx = x + dir[i][0], dy = y + dir[i][1];
if (dx <= 0 || dy <= 0 || dx > n || dy > n || mp[dx][dy] == 'x' || vis[dx][dy]) continue;
vis[dx][dy] = 1;
if (pos == -1 || i == pos) {
dfs(dx, dy, i, cnt);
}
else {
if ((i == 0 && pos == 1) || (i == 1 && pos == 0) || (i == 2 && pos == 3) || (i == 3 && pos == 2)) {
dfs(dx, dy, i, cnt + 2);
}
else {
dfs(dx, dy, i, cnt + 1);
}
}
vis[dx][dy] = 0;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
//clock_t c1 = clock();
//===========================================================
read(n);
rep(i, 1, n) {
rep(j, 1, n) {
cin >> mp[i][j];
if (mp[i][j] == 'A') {
xa = i, ya = j;
}
if (mp[i][j] == 'B') {
xb = i, yb = j;
}
}
}
vis[xa][ya] = 1;
dfs(xa, ya, -1, 0);
if (ans >= n * n) {
puts("-1");
}
else {
write(ans);
}
//===========================================================
//std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}最短路：
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=((ans%mod)*(a%mod))%mod;
a=((a%mod)*(a%mod))%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
#define int ll
int n;
const int maxn=105;
char mp[maxn][maxn];
struct Edge{
int to,next,w;
}e[maxn*maxn*5*2];
int head[maxn*maxn*5],cnt;
void add(int x,int y,int w){
e[cnt].w=w;
e[cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt++;
e[cnt].w=w;
e[cnt].to=x;
e[cnt].next=head[y];
head[y]=cnt++;
}
int dis[maxn*maxn*5*2];
struct node{
int u,dis;
node(int uu,int dd){
u=uu;
dis=dd;
}
};
auto cmp=[](const node&a,const node&b){
return a.dis>b.dis;
};
int vis[maxn*maxn*5*2];
priority_queue<node,vector<node>,decltype(cmp)> que(cmp);
int dij(int s,int end){
memset(dis,inf,sizeof(dis));
dis[s]=0;
que.push(node(s,0));
while(!que.empty()){
node a=que.top();
que.pop();
int u=a.u;
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
que.push(node(v,dis[v]));
}
}
}
return dis[end];
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//===========================================================
memset(head,-1,sizeof(head));
read(n);
rep(i,1,n){
rep(j,1,n){
cin>>mp[i][j];
}
}
/*rep(i,1,n){
rep(j,1,n){
cerr<<mp[i][j];
}
cerr<<endl;
}*/
//0 left 1 up 2 right 3 down
rep(i,1,n){
rep(j,1,n){
if(mp[i][j]=='x') continue;
int left=(i-1)*n+j,up=(i-1)*n+j+1*n*n,right=(i-1)*n+j+2*n*n,down=(i-1)*n+j+3*n*n;
add(left,up,1),add(up,right,1),add(right,down,1),add(down,left,1);
add(left,right,0),add(up,down,0);
if(j>1){
int lr=(i-1)*n+j-1+2*n*n;
add(lr,left,0);
}
if(j<n){
int rl=(i-1)*n+j+1+0*n*n;
add(rl,right,0);
}
if(i>1){
int ud=(i-2)*n+j+3*n*n;
add(up,ud,0);
}
if(i<n){
int du=(i+0)*n+j+1*n*n;
add(du,down,0);
}
if(mp[i][j]=='A'){
int ss=0;
add(ss,left,0);
add(ss,right,0);
add(ss,up,0);
add(ss,down,0);
}
if(mp[i][j]=='B'){
int se=4*n*n+1;
add(se,left,0);
add(se,right,0);
add(se,up,0);
add(se,down,0);
}
}
}
int ans=dij(0,4*n*n+1);
if(ans>=n*n){
puts("-1");
}
else{
write(ans);
}
//===========================================================
return 0;
}B.牛牛的零食
这道题很明显是组合数学。他要求的是[a,b]范围内符合条件的数，一般这种都是转化为cal(b)-cal(a-1)，因为在1~n的范围内求某个数a的倍数的个数可以用n/a得到。这里还有其他的附加条件：不能被其它数整除，那么，考虑容斥原理：对于一个数n，可以被8整除的有n/8个，之后，不能被其他的数整除，其实应该要减去的是既是8的倍数，又是该数的倍数的，所以是lcm(8,x)，按这样去除之后，显然会去多，所以再加回来，例如：
3
7764 6082 462
那就是，这个过程可以用dfs实现（也可以用队列数组或者二进制）。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=((ans%mod)*(a%mod))%mod;
a=((a%mod)*(a%mod))%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
#define int ll
int n,xs[20];
int a,b,ans;
void dfs(int x,int l,int s,int sig){
if(l>n){
ans+=sig*x/s;
return ;
}
dfs(x,l+1,s,sig);
dfs(x,l+1,(s*xs[l])/gcd(s,xs[l]),-sig);
}
int cal(int x){
ans=0;
dfs(x,1,8,1);
return ans;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//===========================================================
read(n);
rep(i,1,n) read(xs[i]);
read(a),read(b);
write(cal(b)-cal(a-1));
//===========================================================
return 0;
}C.牛牛的最美味和最不美味的零食
这道题的正确做法应该是记住树的siz，然后根据左子树siz的大小选择跳左子树还是跳右子树。需要注意的是，在eat的时候，需要先用连个变量存下左子树的siz和右子树的siz，因为eat之后siz会改变，可能导致一次吃了两个糖，当然，也可以用else if，个人习惯。
另一种做法是看大佬的：用树状数组记录前面吃掉的糖果数，每次query的时候，二分查找到idx1-前缀和(idx1)==i和idx2-前缀和(idx2)==j，这个就是现在要找的这个区间的对应原始的断点的位置，之后就像普通查找一样query原始端点就行了，但复杂度会高一些。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=((ans%mod)*(a%mod))%mod;
a=((a%mod)*(a%mod))%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
#define int ll
#define lson (rt<<1)
#define rson (rt<<1|1)
#define pii pair<int,int>
int n,m;
const int maxn=1e6+10;
struct node{
int siz,l,r,mi,ma;
}tree[maxn<<2];
void pushup(int rt){
tree[rt].ma=max(tree[lson].ma,tree[rson].ma);
tree[rt].mi=min(tree[lson].mi,tree[rson].mi);
tree[rt].siz=(tree[lson].siz+tree[rson].siz);
}
void build(int l,int r,int rt){
tree[rt].l=l,tree[rt].r=r;
if(l==r){
read(tree[rt].ma);
tree[rt].mi=tree[rt].ma;
tree[rt].siz=1;
return ;
}
int m=(l+r)>>1;
build(l,m,lson);
build(m+1,r,rson);
pushup(rt);
}
void eat(int tar,int rt){
int l=tree[rt].l,r=tree[rt].r;
if(l==r){
tree[rt].siz=0;
tree[rt].ma=-inf;
tree[rt].mi=inf;
return;
}
int siz1=tree[lson].siz;
if(tar<=siz1) eat(tar,lson);
if(tar>siz1) eat(tar-siz1,rson);
pushup(rt);
}
pii query(int ql,int qr,int rt){
if(ql<=1&&qr>=tree[rt].siz){
return make_pair(tree[rt].mi,tree[rt].ma);
}
int ma=-inf,mi=inf;
if(ql<=tree[lson].siz){
pii t=query(ql,qr,lson);
ma=max(ma,t.second);
mi=min(mi,t.first);
}
if(qr>tree[lson].siz){
pii t=query(ql-tree[lson].siz,qr-tree[lson].siz,rson);
mi=min(mi,t.first);
ma=max(ma,t.second);
}
return make_pair(mi,ma);
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//===========================================================
read(n),read(m);
build(1,n,1);
while(m--){
int opt;read(opt);
if(opt==1){
int k;read(k);
eat(k,1);
}
if(opt==2){
int i,j;read(i),read(j);
pii ans=query(i,j,1);
write(ans.first),putchar(' '),write(ans.second),putchar('\n');
}
}
//===========================================================
return 0;
}D.瘦了的牛牛去旅游
这道题像不大明白Orz
首先看到数据范围，发现很小，又和最短路有关，我们想到的应该是Floyd。但这里求的是密度，我们还缺一个数，就是这条最短路他经过的路径数。俗话说的话：维度不够，再加一维？空间上也还可以，所以，我们就得到了整个状态dp[i][j][k],表示从i到j经过k条路径的最短路。这里其实算是一个分阶段贪心：对每个k，我们都选择i到j的最短路，记录下下来，然后，再遍历所有的k，选择其中最小的dp[i][j][k]/k作为ans[i][j]。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=((ans%mod)*(a%mod))%mod;
a=((a%mod)*(a%mod))%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
const int maxm=1e3+10;
const int maxn=55+10;
int n,m,q;
int G[maxn][maxn];
int dp[maxn][maxn][maxn];
double ans[maxn][maxn];
#include <iomanip>
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//===========================================================
read(n),read(m);
memset(G,inf,sizeof(G));
memset(dp,inf,sizeof(dp));
rep(i,0,n){
rep(j,0,n){
ans[i][j]=(double) inf;//ans是double型，需要手写循环初始化
}
}
while(m--){
int a,b,c;
read(a),read(b),read(c);
G[a][b]=min(G[a][b],c);
dp[a][b][1]=G[a][b];
}
rep(i,1,n) dp[i][i][0]=0;//边界条件
rep(l,2,n){//枚举经过的路径数
rep(k,1,n){//枚举中转结点
rep(i,1,n){//枚举起点
rep(j,1,n){//枚举中点
dp[i][j][l]=min(dp[i][j][l],dp[i][k][l-1]+G[k][j]);
}
}
}
}
rep(i,1,n){
rep(j,1,n){
rep(k,1,n){
if(dp[i][j][k]!=inf) ans[i][j]=min((1.0*dp[i][j][k])/k,ans[i][j]);//更新ans
}
}
}
int q;read(q);
while(q--){
int a,b;read(a),read(b);
if(ans[a][b]!=inf)cout<<fixed<<setprecision(3)<<ans[a][b]<<endl;
else puts("OMG!");
}
//===========================================================
return 0;
}E.只能吃土豆的牛牛
看到给的是3^n,就想到和二进制有关。我是这样想的：他要的是第k大，又是这样的3^n的形式，那么，可以看作是二进制串1、10、11……之间的大小比较，如，k=3，可以看作是第一小的1，第二小的10之后的第三小数11，这里的01串和这些土豆拿一部分出来的和是意义对应的，也就是说，一个二进制串可以对应某几个土豆的质量和，而二进制串的大小和土豆质量也是正相关的关系，所以，我们求第4大的土豆质量和，完全可以看到是100串，也就是这样取的结果（语无伦次）。所以，只需要对k进行二进制拆解就行了。
#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
template<typename T> void read(T &x)
{
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
ll ans=1;
while(n){
if(n&1) ans=(ans*a)%mod;
a=a*a%mod;
n>>=1;
}
return ans%mod;
}
//==============================================================
ll t,k;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
//clock_t c1 = clock();
//===========================================================
read(t);
int kase=0;
while(t--){
ll ans=0;
read(k);
ll base=1;
while(k){
if(k&1) ans+=base;
base*=3;
k>>=1;
}
printf("Case #%d: %lld\n",++kase,ans);
}
//===========================================================
//std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
return 0;
}
京公网安备 11010502036488号