#### 比赛地址

– F
– Acrostic
– Ordinary Beauty
– Saving Snuuk
– Plus Graph

AB不讲。

### C – Ordinary Beauty

#### Statement

Let us define the beauty of a sequence $(a_1,… ,a_n)$ as the number of pairs of two adjacent elements in it whose absolute differences are $d$.
For example, when $d=1$, the beauty of the sequence $(3, 2, 3, 10, 9)$ is $3$.

There are a total of $n^m$sequences of length $m$ where each element is an integer between $1$ and $n$ (inclusive).
Find the beauty of each of these $n^m$ sequences, and print the average of those values.

#### Code

#include
#define ll long long
using namespace std;
ll n, m, d;
int main(){
scanf("%lld%lld%lld", &n, &m, &d);
double temp;
if(d==0) temp=n;
else temp=(n-d)*2;//temp是一个间隔的所有情况之和，平均值要除以 n^2
printf("%.10lf
", (double)(m-1)/n*temp/n);//防止卡精度
}

### D – Saving Snuuk

#### Statement

Kenkoooo is planning a trip in Republic of Snuke.
In this country, there are $n$ cities and $m$ trains running.
The cities are numbered $1$ through $n$, and the $i$-th train connects City $u_i$ and $v_i$ bidirectionally.
Any city can be reached from any city by changing trains.

Two currencies are used in the country: yen and snuuk.
Any train fare can be paid by both yen and snuuk.
The fare of the $i$-th train is $a_i$ yen if paid in yen, and $b_i$ snuuk if paid in snuuk.

In a city with a money exchange office, you can change $1$ yen into $1$ snuuk.
However, when you do a money exchange, you have to change all your yen into snuuk.
That is, if Kenkoooo does a money exchange when he has $X$ yen, he will then have $X$ snuuk.
Currently, there is a money exchange office in every city, but the office in City $i$ will shut down in $i$ years and can never be used in and after that year.

Kenkoooo is planning to depart City $s$ with $10^{15}$ yen in his pocket and head for City $t$, and change his yen into snuuk in some city while traveling.
It is acceptable to do the exchange in City $s$ or City $t$.

Kenkoooo would like to have as much snuuk as possible when he reaches City $t$ by making the optimal choices for the route to travel and the city to do the exchange.
For each $i=0,…,n-1$, find the maximum amount of snuuk that Kenkoooo has when he reaches City $t$ if he goes on a trip from City $s$ to City $t$ after $i$ years.
You can assume that the trip finishes within the year.

#### Code

#include
#define maxn 200010
#define INF 0x3f3f3f3f
using namespace std;
struct Edge{
int to,next,val;
Edge(int a=0,int b=0,int c=0){
to=a,next=b,val=c;
}
}l[maxn<<1];
long long dis[maxn],res[maxn];
void SPFA(int s,int k){
queueq;int vis[maxn];
memset(vis,0,sizeof(vis));
memset(dis,INF,sizeof(dis));
q.push(s),dis[s][k]=0;
while(!q.empty()){
int hq=q.front();q.pop();vis[hq]=0;
int v=l[i][k].to;
if (dis[v][k]>dis[hq][k]+l[i][k].val){
dis[v][k]=dis[hq][k]+l[i][k].val;
if (!vis[v]) vis[v]=1,q.push(v);
}
}
}
for (int i=1;i<=n;i++) res[i]+=dis[i][k];
}
void add(int a,int b,int c,int k){
}
int main(){
ios::sync_with_stdio(false);
int s,t; cin>>n>>m>>s>>t;
for (int i=1;i<=m;i++){
int x,y,a,b;
cin>>x>>y>>a>>b;
for (int i=1;i<=n;i++) cout<<1000000000000000-res[i]<
 E - Plus Graph Statement Kenkoooo found a simple connected graph. The vertices are numbered $1$ through $n$. The $i$-th edge connects Vertex $u_i$ and $v_i$, and has a fixed integer $s_i$. Kenkoooo is trying to write a positive integer in each vertex so that the following condition is satisfied: For every edge $i$, the sum of the positive integers written in Vertex $u_i$ and $v_i$ is equal to $s_i$. Find the number of such ways to write positive integers in the vertices. Idea 
 Share Show Comments 【CodeVS 1163】“访问”艺术馆（gallery）/ 题解 Origin Statement Peel was a famous pirate painter. After months of careful… 09 Jul 2018 【Codevs 1768】种树 / 题解 Origin Statement 为了绿化乡村，H村积极响应号召，开始种树了。 H村里有n幢房屋，这些屋子的排列顺序很有特点，在一条直线上。于是方便起见，我们给它们标上1~n。树就种在房子前面的空地上。… 08 Jul 2018 
 
 
 Topics Thought: 30 Study: 26 Selected: 26 Zepto's © 2022 Sponsor Data & privacy Contact → Published with Ghost • Theme Attila • System theme 
 $(document).ready(function () { var viewport =$(window); var post = $('.post-content'); // Responsive videos with fitVids post.fitVids(); // Format code blocks and add line numbers function codestyling() {$('pre code').each(function(i, e) { // Code highlight hljs.highlightBlock(e); // No lines for plain text blocks if (!$(this).hasClass('language-text')) { var code =$(this); // Calculate amount of lines var lines = code.html().split(/\n(?!$)/g).length; var numbers = []; if (lines > 1) { lines++; } for (i = 1; i < lines; i++) { numbers += '<span class="line" aria-hidden="true">' + i + '</span>'; } code.parent().append('<div class="lines">' + numbers + '</div>'); } }); } codestyling(); // Reading progress bar on window top function readingProgress() { var postBottom = post.offset().top + post.height(); var viewportHeight = viewport.height(); var progress = 100 - (((postBottom - (viewport.scrollTop() + viewportHeight) + viewportHeight / 3) / (postBottom - viewportHeight + viewportHeight / 3)) * 100);$('.progress-bar').css('width', progress + '%'); (progress > 100) ? $('.progress-container').addClass('complete'):$('.progress-container').removeClass('complete'); } readingProgress(); // Trigger reading progress viewport.on({ 'scroll': function() { readingProgress(); }, 'resize': function() { readingProgress(); }, 'orientationchange': function() { readingProgress(); } }); // Check if disqus is defined by code injection if (typeof disqus === 'undefined') { // hide comment section $('.post-comments').css({ 'display': 'none' }); } else {$('#show-disqus').on('click', function() { $.ajax({ type: "GET", url: "//" + disqus + ".disqus.com/embed.js", dataType: "script", cache: true });$(this).parent().addClass('activated'); }); } });