100+100+100+80+100=480
重复局面
题目大意
依次给定(n)个国际象棋局面,依次回答每个局面是第几次出现。
解题思路
拿map
记录下每个局面,统计计数即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin >> n;
map qwq;
while(n--){
string s;
for(int i = 0; i > a;
s += a;
}
qwq[s] ++;
cout
矩阵运算
题目大意
给定(n times d)的矩阵 (q, k, v),一个 (n)维向量 (w),计算 ((w cdot (q times k^{T})) times v) 的结果。
(n leq 10^4, d leq 20)
解题思路
(q times k^{T})的结果是 (n times n)的矩阵,因为计算结果可能会超出 (int)范围, (10^8)的 (long long)内存有 (700MB+ geq 512MB),因此不能按此计算。
注意矩阵乘法具有结合律,而且点乘 (cdot)不会影响此处的结果,因此我们可以改为算 (w cdot q times (k^{T} times v)) ,这样(k^{T} times v)只有 (d times d)的大小,完全可以储存和计算。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n, d;
cin >> n >> d;
vector> q(n, vector(d, 0)), k(n, vector(d, 0)), v(n, vector(d, 0));
vector w(n, 0);
for(auto &i : q)
for(auto &j : i)
cin >> j;
for(auto &i : k)
for(auto &j : i)
cin >> j;
for(auto &i : v)
for(auto &j : i)
cin >> j;
for(auto &i : w)
cin >> i;
vector> tmp(d, vector(d, 0)), tmp2(n, vector(d, 0));
for(int i = 0; i
解压缩
题目大意
给定了一个压缩后的数据,以及解压的规则,输出解压后的数据。
解题思路
就按照规则模拟即可,注意大端模式和小端模式的数据解析。
神奇的代码
#include
using namespace std;
using LL = long long;
#define LOWER 3
#define CONST_VAL 0
#define BACK_SHORT 1
#define BACK_LONG 2
LL get_num(char c){
if (isdigit(c))
return c - '0';
else
return c - 'a' + 10;
}
LL get_sz(const string& s, int& pos, int len){
LL sum = 0;
for(int i = pos; i > 7) & 1);
}
LL remove_up(LL num){
if (up_zero(num))
return num;
else
return num ^ (1 > n;
n = (n + 7) / 8;
string s;
for(int i = 0; i > a;
s += a;
}
int id = 0;
LL sz = 0;
LL ji = 1;
while(true){
int sign = get_sz(s, id, 2);
sz += ji * remove_up(sign);
ji *= 128;
if (up_zero(sign)){
break;
}
}
string ans;
while(ans.size() > 2);
if (len > 2) & 7) + 4;
int o = ((sign >> 5) = len){
ans += ans.substr(ans.size() - o, len);
}else{
int pos = ans.size() - o;
string tmp;
while(len){
tmp += ans[pos];
pos ++;
if (pos == ans.size())
pos -= o;
-- len;
}
ans += tmp;
}
}else if ((sign & LOWER) == BACK_LONG){
int len = (sign >> 2) + 1;
int o = get_sz_small(s, id, 4);
len *= 2;
o *= 2;
if (o >= len){
ans += ans.substr(ans.size() - o, len);
}else{
int pos = ans.size() - o;
string tmp;
while(len){
tmp += ans[pos];
pos ++;
if (pos == ans.size())
pos -= o;
-- len;
}
ans += tmp;
}
}
}
for(int i = 0; i
电力网络
题目大意
给定一张(n)个点 (m)条边的无向连通图,要求给每个点规定一个颜色,共有(k)种颜色可选,使得总代价最小。
总代价包括点的代价和边的代价,点的代价即选定该点的颜色对应的代价。边的代价由每条边两点颜色决定,以矩阵形式给出。
五个子任务:
- 点数(leq 6),颜色数 (leq 10)
- 点数 (leq 10^4),颜色数 (leq 10),一棵树
- 点数 (leq 10^4),颜色数 (leq 10),一棵基环树
- 点数 (leq 10^4),颜色数 (leq 10),一个图,但去掉其中的某个点(D)及其连边,变成一棵树,且与点(D)相连的点都是以某个点 (S)为根的叶子
- 点数 (leq 10^4),颜色数 (leq 10),一个图,但度数(> 2)的点数 (leq 6)
解题思路
第一个子任务,直接暴力,枚举每个点的颜色然后求代价的最小值,复杂度为(O(k^n + n + m))
第二个子任务,设(dp[i][j])表示 点(i) 的颜色为(j)的最小代价,枚举儿子的颜色,树形(dp)转移。复杂度为(O(nk^2))
第三个子任务,找到环上的任意一条边((u, v)),枚举 (u)的颜色(消除后效性),然后以 (v)为根( (u)也行)做上述树形 (dp)即可。复杂度为(O(nk^3)),如何找到环上一条边,跑一下并查集即可。
第四个子任务,找到点(D),然后枚举点(D)的颜色(同样消除后效性),然后以不与点(D)有连边的点(s)做上述树形 (dp)即可。复杂度为(O(nk^3)),如何找到点(D),首先统计每个点的度数,点(D)的度数(d)满足 (m – d = n – 2)(数据可能水了,有这个条件就够了,感觉单满足这个条件还不够,可能会存在把 点(D)去掉后不联通),然后与点 (D)相连的点的度数都为 (2)(为叶子)
第五个子任务,如果全部度数(,那么随便枚举一个点的颜色,然后上述树形 (dp)即可。否则找到度数(> 2)的点,剩下的都是度数为(2,1)的点,它们仅可能形成一条链(不可能是环),然后(C_6^2)枚举每条链,再花 (O(k))枚举每条链的一端颜色,做一遍上述树形 (dp),然后再枚举每个度数 (> 2)的颜色,求最小值。复杂度为 (O(k^6 + nk^3)),但感觉不太好写,也没时间写了(
神奇的代码
#include
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n, k, m;
cin >> n >> m >> k;
vector> pcost(n, vector(k));
for(auto &i : pcost)
for(auto &j : i)
cin >> j;
vector>> edge(n);
vector> edges(m);
vector> ecost(m, vector(k * k));
for(int i = 0; i > u >> v;
edges[i] = {u, v};
edge[u].push_back({v, i});
edge[v].push_back({u, i});
for(auto &j : ecost[i])
cin >> j;
}
if (n used(n);
LL ans = inf;
LL tmp = 0;
function dfs = [&](int x){
if (x == n){
LL back = tmp;
for(int i = 0; i > dp(n, vector(k, 0));
function dfs = [&](int u, int fa){
for(auto e : edge[u]){
int v = e[0], id = e[1];
if (v == fa)
continue;
dfs(v, u);
for(int i = 0; i id(n);
iota(id.begin(), id.end(), 0);
int ignore = 0;
function findfa = [&](int x){
return x == id[x] ? x : id[x] = findfa(id[x]);
};
for(int i = 0; i > dp(n, vector(k, 0));
LL ans = inf;
int fixed = edges[ignore][0], st = edges[ignore][1];
for(int col = 0; col dfs = [&](int u, int fa){
for(auto e : edge[u]){
int v = e[0], id = e[1];
if (v == fa || id == ignore)
continue;
dfs(v, u);
for(int i = 0; i du(n);
for(int i = 0; i forbid(n, 0);
for(auto &e : edge[target]){
int v = e[0];
forbid[v] = 1;
}
int st = 0;
while(st == target || forbid[st])
++ st;
vector> dp(n, vector(k, 0));
LL ans = inf;
for(int col = 0; col dfs = [&](int u, int fa){
for(auto e : edge[u]){
int v = e[0], id = e[1];
if (v == fa)
continue;
if (v != target)
dfs(v, u);
for(int i = 0; i
闪耀循环
题目大意
给定(n)个字符串(s_i) 以及一个字符串(t),对于每个字符串(s_i),回答以下问题 :
依次选择若干个串(s_j, s_k, s_l, …),组成串 (s_i,s_j,s_k,s_l,…),要求前一串的末尾字母和后一串的开头字母相同,第一个串的开头字母和最后一个串的末尾字母相同,字符串 (t)的每个字母都在这些串组成的大串出现过。求最小代价。
代价为每个串的长度 (-1)的和。
(|t| leq 10)
解题思路
对于每个串,能够提供的信息就是首末字母和包含的字符串(t)的字母情况。
建一张图,点是每个字母,对于一个串 (s_i = a…b),连一条边 (b to a),边权有两个,一个是串长度 (-1),另一个是包含的字符串 (t)的字母情况,因为 (|t| leq 10),可以二进制位压缩成一个数。
然后设 (dis[i][j][k])表示最终回到点 (i),当前在点 (j),已经获得到的字符串 (t)的字母情况为 (k),最终到点 (i)且字母情况为满(即包括了 (t)的所有字母)的最小代价。
然后从 (dis[i][i][(1 开始 (dijkstra)搜。枚举另边,不断消去第三维的值。
对于每个串(s_i)的信息(a, b, sign)(包含串 (t)字母的情况),答案就是(dis[a][b][c] + |s_i| – 1),但由于我们是从终点开始搜的,对于第三维是能消去就先消去,但最后求答案是从起点考虑,虽然说经过了这条边,包含串 (t)的字母情况变成 (sign),但其中有的字母可以后面的串得到,从终点搜到这里会已经消去,因此这里的(c)应该遍历(sign)的所有子集,取最小值。
状态数是(O(2^{10} times 26 times 26)),但每个状态的连边实际上是有 (O(n))的数量集,转移代价可能比较大,但或许实际上没那么大(或者数据水了),就过了。
神奇的代码
#include
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
string t;
cin >> n >> t;
vector id(26, -1);
int cnt = 0;
for(auto &i : t){
id[i - 'a'] = cnt;
++ cnt;
}
vector>> edge(26);
vector> query(n);
for(int i = 0; i > s;
int st = s.front() - 'a';
int ed = s.back() - 'a';
int sign = 0;
int len = s.size() - 1;
for(auto &i : s){
if (id[i - 'a'] != -1){
sign |= (1 >> dis(26, vector>(26, vector(up, inf)));
for(int i = 0; i > team;
team.push({0, i, up - 1});
while(!team.empty()){
array top = team.top();
team.pop();
LL distance = -top[0];
int u = top[1], sign = top[2];
if (dis[i][u][sign] != distance)
continue;
for(auto &e : edge[u]){
int v = e[0], len = e[1], si = e[2];
int nxtsign = (sign ^ (sign & si));
if (dis[i][v][nxtsign] > distance + len){
dis[i][v][nxtsign] = distance + len;
team.push({-dis[i][v][nxtsign], v, nxtsign});
}
}
}
}
for(int i = 0; i
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net