ABC051

[ABC051B] Sum of Three Integers

题面翻译

题目描述

有两个整数 $K$ , $S$

求有几种方案使得三个非负整数 $X$ , $Y$ , $Z$ 之和= $S$ 并且均 $\leq K$

输入格式

两个正整数 $K$ , $S$ , 见题目描述。

输出格式

一个整数，表示方案数

题目描述

$ 2 $ つの整数 $ K,S $ が与えられます。
$ 3 $ つの変数 $ X,Y,Z $ があり、$ 0≦X,Y,Z≦K $ を満たす整数の値を取ります。
$ X + Y + Z = S $ を満たす $ X,Y,Z $ への値の割り当ては何通りありますか。

输入格式

入力は以下の形式で標準入力から与えられる。

$ K $ $ S $

输出格式

問題文の条件を満たす $ X,Y,Z $ の組が何通りあるか出力せよ。

样例 #1

样例输入 #1
2 2
样例输出 #1
6
样例 #2

样例输入 #2
5 15
样例输出 #2
1
提示

制約

$ 2≦K≦2500 $

$ 0≦S≦3K $

$ K,S $ は整数である。

Sample Explanation 1

問題文の条件を満たす $ X,Y,Z $ の組は以下の $ 6 $ 通りです。 - $ X = 0, Y = 0, Z = 2 $ - $ X = 0, Y = 2, Z = 0 $ - $ X = 2, Y = 0, Z = 0 $ - $ X = 0, Y = 1, Z = 1 $ - $ X = 1, Y = 0, Z = 1 $ - $ X = 1, Y = 1, Z = 0 $

Sample Explanation 2

$ X + Y + Z $ の最大値は $ 15 $ であり、それを満たす組は $ 1 $ 通りです。

思路

直接枚举不行，所以我们可以只要枚举X，Y，然后判断是否存在符合要求的Z即可，注意X,Y,Z的范围

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
map<ll,ll> m;
ll qpower(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return ans;
}
ll solve(ll x){
    if(m[x])return m[x];
    return m[x]=(solve(x/2)+solve((x-1)/2)+solve((x-2)/2))%mod;
}
int main(){
    ios::sync_with_stdio(false);
    int k,s;cin>>k>>s;
    int ans=0;
    for(int i=0;i<=k;i++){
        for(int j=0;j<=k;j++){
            if(i+j<=s&&s-j-i<=k)ans++;
        }
    }
    cout<<ans;
    return 0;
}

[ABC051C] Back and Forth

题面翻译

在平面直角坐标系中，有点 $A（sx,sy）$ 和点 $B（tx,ty）$ 保证 $sx<tx$，$sy<ty$ 并且 $sx,sy,tx,ty$ 都为整数。

在 $A$ 点有一只海豚，它每次可以向上下左右其中一个方向移动一个单位长度。这只海豚想从 $A$ 点到 $B$ 点再回到 $A$ 点再到 $B$ 点再回到 $A$ 点。

要求：除了 $A,B$ 点以外，所有格点都不能走第二遍。海豚不能斜着走。

输出一个字符串 S 表示海豚的最短路径， S 中只包括 $U,R,D,L$。

$U$：向上走一个单位长度。

$R$：向右走一个单位长度。

$D$：向下走一个单位长度。

$L$：向左走一个单位长度。

输入格式：

一行，$sx,sy,tx,ty$。

输出格式：

一行，字符串 S。

如果有多个最短路径，输出其中任意一个。

Translate by @sqh_let_it_be

题目描述

イルカは $ x $ 軸正方向を右、$ y $ 軸正方向を上とする 2 次元座標平面にいます。
イルカは現在点 $ (sx,sy) $ にいて、$ 1 $ 秒あたり上下左右に距離 $ 1 $ だけ進むことができます。
このとき、移動前と移動後の $ x $ 座標、$ y $ 座標はともに整数でなければなりません。
イルカはここから $ sx と sy を満たす点 (tx,ty) $ に行き、その後点 $ (sx,sy) $ に戻り、また点 $ (tx,ty) $ に行き、その後点 $ (sx,sy) $ に戻ります。
このとき、イルカは点 $ (sx,sy) $ と点 $ (tx,ty) $ を除いて、途中で同じ座標を複数回通らないように移動しなければなりません。
このような条件を満たすイルカの最短経路を $ 1 $ つ求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ sx $ $ sy $ $ tx $ $ ty $

输出格式

イルカの最短経路を表す文字列 $ S $ を出力せよ。
$ S $ の $ i $ 番目の文字はイルカの $ i $ 番目の移動を表す。
イルカの各方向への移動を表す文字の対応関係は以下のとおりである。

U: 上方向

D: 下方向

L: 左方向

R: 右方向

条件を満たすような最短経路が複数ある場合、そのうちどれか $ 1 $ つを出力せよ。

样例 #1

样例输入 #1
0 0 1 2
样例输出 #1
UURDDLLUUURRDRDDDLLU
样例 #2

样例输入 #2
-2 -2 1 1
样例输出 #2
UURRURRDDDLLDLLULUUURRURRDDDLLDL
提示

制約

$ -1000≦ sx $

$ -1000≦ sy $

$ sx,sy,tx,ty $ は整数である。

Sample Explanation 1

以下に示す移動経路が最短経路の $ 1 $ つです。 - $ 1 $ 回目の $ (sx,sy) $ から $ (tx,ty) $ への移動: $ (0,0) $ → $ (0,1) $ → $ (0,2) $ → $ (1,2) $ - $ 1 $ 回目の $ (tx,ty) $ から $ (sx,sy) $ への移動: $ (1,2) $ → $ (1,1) $ → $ (1,0) $ → $ (0,0) $ - $ 2 $ 回目の $ (sx,sy) $ から $ (tx,ty) $ への移動: $ (0,0) $ → $ (-1,0) $ → $ (-1,1) $ → $ (-1,2) $ → $ (-1,3) $ → $ (0,3) $ → $ (1,3) $ → $ (1,2) $ - $ 2 $ 回目の $ (tx,ty) $ から $ (sx,sy) $ への移動: $ (1,2) $ → $ (2,2) $ → $ (2,1) $ → $ (2,0) $ → $ (2,-1) $ → $ (1,-1) $ → $ (0,-1) $ → $ (0,0) $

思路

直接暴力模拟过程即可。

具体看大佬的图示：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
map<ll,ll> m;
ll qpower(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return ans;
}
ll solve(ll x){
    if(m[x])return m[x];
    return m[x]=(solve(x/2)+solve((x-1)/2)+solve((x-2)/2))%mod;
}
int main(){
    ios::sync_with_stdio(false);
    int sx,sy,tx,ty;cin>>sx>>sy>>tx>>ty;
    int x=tx-sx,y=ty-sy;
    for(int i=1;i<=y;i++)cout<<"U";
    for(int i=1;i<=x;i++)cout<<"R";
    for(int i=1;i<=y;i++)cout<<"D";
    for(int i=1;i<=x;i++)cout<<"L";
    cout<<"L";
    for(int i=1;i<=y+1;i++)cout<<"U";
    for(int i=1;i<=x+1;i++)cout<<"R";
    cout<<"DR";
    for(int i=1;i<=y+1;i++)cout<<"D";
    for(int i=1;i<=x+1;i++)cout<<"L";
    cout<<"U";
    return 0;
}

[ABC051D] Candidates of No Shortest Paths

题面翻译

给定一个 $n$ 个点，$m$ 条边的无重边无自环的加权无向连通图，问全源最短路有几条边没被用到。

题目描述

自己ループと二重辺を含まない $ N $ 頂点 $ M $ 辺の重み付き無向連結グラフが与えられます。
$ i (1≦i≦M) $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を距離 $ c_i $ で結びます。
ここで、自己ループは $ a_i = b_i (1≦i≦M) $ となる辺のことを表します。
また、二重辺は $ (a_i,b_i)=(a_j,b_j) $ または $ (a_i,b_i)=(b_j,a_j) (1≦i < j≦M) $ となる辺のことを表します。
連結グラフは、どの異なる $ 2 $ 頂点間にも経路が存在するグラフのことを表します。
どの異なる $ 2 $ 頂点間の、どの最短経路にも含まれない辺の数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ : $ $ a_M $ $ b_M $ $ c_M $

输出格式

グラフ上の、どの異なる $ 2 $ 頂点間の、どの最短経路にも含まれない辺の数を出力せよ。

样例 #1

样例输入 #1
3 3
1 2 1
1 3 1
2 3 3
样例输出 #1
1
样例 #2

样例输入 #2
3 2
1 2 1
2 3 1
样例输出 #2
0
提示

制約

$ 2≦N≦100 $

$ N-1≦M≦min(N(N-1)/2,1000) $

$ 1≦a_i,b_i≦N $

$ 1≦c_i≦1000 $

$ c_i $ は整数である。

与えられるグラフは自己ループと二重辺を含まない。

与えられるグラフは連結である。

Sample Explanation 1

この入力例で与えられるグラフにおける、全ての異なる $ 2 $ 頂点間の最短経路は以下の通りです。 - 頂点 $ 1 $ から頂点 $ 2 $ への最短経路は、頂点 $ 1 $ → 頂点 $ 2 $ で経路長は $ 1 $ - 頂点 $ 1 $ から頂点 $ 3 $ への最短経路は、頂点 $ 1 $ → 頂点 $ 3 $ で経路長は $ 1 $ - 頂点 $ 2 $ から頂点 $ 1 $ への最短経路は、頂点 $ 2 $ → 頂点 $ 1 $ で経路長は $ 1 $ - 頂点 $ 2 $ から頂点 $ 3 $ への最短経路は、頂点 $ 2 $ → 頂点 $ 1 $ → 頂点 $ 3 $ で経路長は $ 2 $ - 頂点 $ 3 $ から頂点 $ 1 $ への最短経路は、頂点 $ 3 $ → 頂点 $ 1 $ で経路長は $ 1 $ - 頂点 $ 3 $ から頂点 $ 2 $ への最短経路は、頂点 $ 3 $ → 頂点 $ 1 $ → 頂点 $ 2 $ で経路長は $ 2 $ したがって、一度も最短経路として使用されていない辺は、頂点 $ 2 $ と頂点 $ 3 $ を結ぶ長さ $ 3 $ の辺のみであるため、$ 1 $ を出力します。

Sample Explanation 2

全ての辺が異なる $ 2 $ 頂点間のある最短経路で使用されます。

思路

$n$只有100，所以直接用$Floyd$即可，再每次记录当前边有没有被松弛掉，如果是第一次松弛就$ans++$。

注意到是无向图，所以$ans$要除以二。

#include<bits/stdc++.h>
using namespace std;
const int N=101;
int n,m,g[N][N],ans;
bool vis[N][N];
int main(){
	scanf("%d%d",&n,&m);
	memset(g,0x3f,sizeof(g));
	for(int i=1,x,y,z;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		g[x][y]=g[y][x]=z,vis[x][y]=vis[y][x]=1;
	}//记录边，并且给边打上标记
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			if(g[i][j]>g[i][k]+g[k][j]){
				if(vis[i][j])ans++,vis[i][j]=0;
                //如果是第一次松弛，ans++
				g[i][j]=g[i][k]+g[k][j];
			}//Floyd模板
	printf("%d",ans>>1);
	return 0;
}