本文主要是介绍2015省赛选拔，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Arc and Point http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4709 几何弱成狗 Block Toy http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4710 3维版本的铺砖，状态压缩dp。 Four coloring of a map http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4714 Giving directions to the tree http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4715 Just another pachinko-like machine http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4718 Biggest Number http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4610 搜索+剪枝，剪枝很弱。 Repairing a Road http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4611 三分+最短路，想出之后扔给队友写。。。 A Shooting Game http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4612 Number of Battlefields http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4613 Infinite Dictionaries http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4614 Tetrahedrons and Spheres http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4615 Road Network http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4190 最短路+dp+拓扑，好题，求经过每一条边的最短路个数，需要深刻理解最短路。 开始写了正反2次dp，超时，其实第二次不需要再从图上拓扑，可以在第一次求最短路的时候把拓扑的先后存在一个数组里即可，具体得看代码。#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1555;
const int maxm = 5155;
typedef __int64 LL;
const int mod = 1000000007;
struct edge
{
int u, v, w, id;
edge(){
}
edge(int u, int v, int w, int id): u(u), v(v), w(w), id(id) {
}
};
struct node
{
int u, d;
node(){
}
node(int u, int d): u(u), d(d) {
}
bool operator < (const node& rhs) const {
if(d != rhs.d)
return d > rhs.d;
return u > rhs.u;
}
};
int n, m;
vector <edge> G[maxn];
int dis[maxn], vis[maxn];
int to[maxn];
LL dp[maxn], dp2[maxn];
LL ans[maxm];
void Dijkstra(int s)
{
memset(dp, 0, sizeof(dp));
memset(dp2, 0, sizeof(dp2));
priority_queue <node> Q;
Q.push(node(s, 0));
memset(dis, 0x3f, sizeof(dis));
memset(vis, false, sizeof(vis));
dis[s] = 0;
dp[s] = 1;
int cnt = 0;
while(!Q.empty())
{
node x = Q.top(); Q.pop();
int u = x.u;
if(vis[u])
continue;
vis[u] = true;
to[++cnt] = u;
for(int i = 0; i < G[u].size(); i++)
{
edge y = G[u][i];
int v = y.v;
if(dis[v] > dis[u] + y.w)
{
dis[v] = dis[u] + y.w;
Q.push(node(v, dis[v]));
dp[v] = dp[u];
}
else if(dis[v] == dis[u] + y.w)
{
dp[v] += dp[u];
dp[v] %= mod;
}
}
}
for(int i = cnt; i >= 1; i--)
{
int u = to[i];
dp2[u] = 1;
for(int j = 0; j < G[u].size(); j++)
{
edge y = G[u][j];
int v = y.v;
int id = y.id;
if(dis[u] + y.w == dis[v])
{
dp2[u] += dp2[v];
dp2[u] %= mod;
ans[id] += dp[u]*dp2[v];
ans[id] %= mod;
}
}
}
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
G[u].push_back(edge(u, v, w, i));
}
for(int i = 1; i <= n; i++)
{
Dijkstra(i);
}
for(int i = 0; i < m; i++)
printf("%I64d\n", ans[i]);
return 0;
}
/*
5 4
1 2 5
2 3 5
3 4 5
5 2 5
4 4
1 2 5
2 3 5
3 4 5
4 1 1
*/#include <cstdio>
#include <cstring>
using namespace std;
const int N = 100009;
typedef __int64 LL;
int A[N], C[N], n;
int low_bit(int x) {
return x&-x;
}
int S(int x){
int res = 0; while (x){res += C[x]; x ^= low_bit(x);}
return res;
}
void M(int x){
while (x <= n){++C[x], x += low_bit(x);}
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &A[i]);
LL ans = 0 ;
for (int i=0,j=1;i<n;i=j,++j){
while (j<n&&A[j]<A[j-1]) ++j; if (i+1<j) ++ans;
for(int k = j-1; k >= i; k--) ans += (i+j-k-1) - S(A[k]), M(A[k]);
}
printf("%I64d\n", ans);
}#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
typedef __int64 LL;
int s1[1000010], s2[1000010];
int l1, l2;
int pos[300], f[1000010];
map <string, int> mp;
char str[1000010];
bool ok1(int x, int y)
{
if(s2[x] == 0 || s2[y] == 0)
return true;
if(s2[x] == s2[y])
return true;
return false;
}
bool ok2(int x, int y)
{
if(s1[x] == 0 && s2[y] == 0)
return true;
else if(s1[x] == s2[y])
return true;
else if(s2[y] == 0 && y-s1[x] < 0)
return true;
return false;
}
void getnext()
{
f[0] = f[1] = 0;
for(int i = 1; i < l2; i++)
{
int j = f[i];
while(j && !ok1(i, j))
j = f[j];
f[i+1] = j+ok1(i, j);
}
}
int find()
{
int j = 0;
for(int i = 0; i < l1; i++)
{
while(j && !ok2(i, j))
j = f[j];
if(ok2(i, j))
j++;
if(j == l2)
return i-l2+2;
}
}
int main()
{
int cnt = 0;
while(scanf("%s", str) != EOF)
{
cnt++;
if(str[0] == '$')
break;
if(mp[str] == 0)
s1[l1++] = 0;
else
s1[l1++] = cnt-mp[str];
mp[str] = cnt;
}
cnt = 0;
mp.clear();
while(scanf("%s", str) != EOF)
{
cnt++;
if(str[0] == '$')
break;
if(mp[str] == 0)
s2[l2++] = 0;
else
s2[l2++] = cnt-mp[str];
mp[str] = cnt;
}
//printf("%d %d\n", l1, l2);
getnext();
/*for(int i = 0; i < l1; i++)
printf("%d ", s1[i]);
puts("");
for(int i = 0; i < l2; i++)
printf("%d ", s2[i]);
puts("");
for(int i = 1; i <= l2; i++)
printf("%d ", f[i]);
puts("");
*/
int ans = find();
printf("%d\n", ans);
return 0;
}
/*
a a a b c d $
x x x y z a $
a a a b c d a b c $
x x x y z a x y z $
a a a b c d a d c $
x y x $
a a a b c d a b c $
x y $
*/这篇关于2015省赛选拔的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
