slove 2/13
rank 252
补题 6/13
----------------------------------------------------------
hdu 6578
http://acm.hdu.edu.cn/showproblem.php?pid=6578
题意：
在给定的n长度的数组中需要填入0-3四个数字，需要满足m个
限制，每个限制的意思是在 
----------------------------------------
四维DP：
每一维表示对0-3四个数字最后一次出现的位置进行排序，第一维就表
示在这四个数中最小的位置，第四维就表示当前位置。
然后因为第四维是滚动的，防止炸内存。
Code：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 105;
const ll mod = 998244353;
vector<pair<int, int>> v[N];
ll dp[N][N][N][2];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
v[i].clear();
for (int i = 1; i <= m; i++)
{
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
v[y].push_back(make_pair(x, z));
}
memset(dp, 0, sizeof(dp));
dp[0][0][0][0] = 1;
for (int now = 1; now <= n; now++)
{
for (int i = 0; i <= now; i++)
for (int j = i; j <= now; j++)
for (int k = j; k <= now; k++)
dp[i][j][k][now & 1] = 0;
for (int i = 0; i <= now; i++)
for (int j = i; j <= now; j++)
for (int k = j; k <= now; k++)
{
(dp[i][j][now - 1][now & 1] += dp[i][j][k][(now & 1) ^ 1]) %= mod;
(dp[i][k][now - 1][now & 1] += dp[i][j][k][(now & 1) ^ 1]) %= mod;
(dp[j][k][now - 1][now & 1] += dp[i][j][k][(now & 1) ^ 1]) %= mod;
(dp[i][j][k][now & 1] += dp[i][j][k][(now & 1) ^ 1]) %= mod;
}
for (int i = 0; i <= now; i++)
for (int j = i; j <= now; j++)
for (int k = j; k <= now; k++)
{
for (int t = 0; t < v[now].size(); t++)
{
if ((i >= v[now][t].first) + (j >= v[now][t].first) + (k >= v[now][t].first) + (now >= v[now][t].first) != v[now][t].second)
dp[i][j][k][now & 1] = 0;
}
}
}
ll ans = 0;
for (int i = 0; i <= n; i++)
for (int j = i; j <= n; j++)
for (int k = j; k <= n; k++)
(ans += dp[i][j][k][n & 1]) %= mod;
printf("%lld\n", ans);
}
return 0;
} hdu 6579
http://acm.hdu.edu.cn/showproblem.php?pid=6579
题意：有一个整数数列，有2种操作，
0 l r : 表示求区间 
1 x : 表示将 x 加在区间最后面，并且区间长度+1。
-----------------------------------------------
题目要求强制在线，维护区间前缀线性基
Code :
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int wei = 31;
struct LB
{
int b[wei], cnt;//cnt是个数
int ind[wei];//ind是下标
LB()
{
cnt = 0;
memset(ind, -1, sizeof(ind));
memset(b, 0, sizeof(b));
}
bool insert(int x, int id)
{
for (int i = wei; i >= 0; i--)
{
if (x & (1LL << i))
{
if (!b[i])
{
b[i] = x;
ind[i] = id;
cnt++;
return true;
}
if (ind[i] < id)
{
swap(ind[i], id);
swap(x, b[i]);
}
x ^= b[i];
}
}
return false;
}
};
const ll mod = 1e9 + 7;
int a;
LB lb[1000005];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
lb[i] = lb[i - 1];
scanf("%d", &a);
lb[i].insert(a, i);
}
ll pre = 0;
int op, l, r;
while (m--)
{
scanf("%d", &op);
if (op == 0)
{
scanf("%d%d", &l, &r);
l = (l ^ pre) % n + 1;
r = (r ^ pre) % n + 1;
if (l > r)
swap(l, r);
ll res = 0;
for (int i = wei; i >= 0; i--)
{
if (lb[r].ind[i] >= l && (res ^ lb[r].b[i]) > res)
res ^= lb[r].b[i];
}
pre = res;
printf("%lld\n", res);
}
else
{
scanf("%d", &l);
l = (l ^ pre);
lb[n + 1] = lb[n];
lb[n + 1].insert(l, n + 1);
n++;
}
}
}
} hdu 6581
http://acm.hdu.edu.cn/showproblem.php?pid=6581
题意：有n辆车，每辆车有长度，距离，速度，后面的车会被前面的车卡，求自己什么时候能到终点。
--------------------------------------
二分时间，遍历每一辆车，就可以知道某一时间各辆车的位置。
slove by jzk
Code：
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-10;
struct node
{
int chang;
int w;
int v;
}in[100005];
int n;
bool check(double k)
{
double dis = in[0].w - in[0].v * k;
dis += in[0].chang;
for (int i = 1; i <= n; i++)
{
double dis1 = in[i].w - in[i].v * k;
if (dis1 < dis)
dis += in[i].chang;
else
dis = dis1 + in[i].chang;
}
dis -= in[n].chang;
if (dis <= 0)
return true;
return false;
}
int main()
{
while (scanf("%d", &n) > 0)
{
for (int i = n; i >= 0; i--)
scanf("%d", &in[i].chang);
for (int i = n; i >= 0; i--)
scanf("%d", &in[i].w);
for (int i = n; i >= 0; i--)
scanf("%d", &in[i].v);
double l = 0, r = 1000000000;
while (l + eps < r)
{
double k = (l + r) / 2;
if (check(k))
r = k;
else
l = k;
}
printf("%.10lf\n", l);
}
} hdu 6582
http://acm.hdu.edu.cn/showproblem.php?pid=6582
题意：使得从点1到点n的最短距离变大的最小花费
----------------------------------------------
dij求出1到其他点的距离，如果一条边的边长=端点到点1的距离之差的绝对值，那么这条边在最短路径上，求出所有在最短路径上的点，跑最小割。
slove by yp
Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX = 1e5 + 5;
const ll INF = 1e17+9;
struct stu {
ll dot;
ll length;
};
bool operator<(stu a, stu b) {
return a.length > b.length;
}
ll n, m, u[MAX], v[MAX], first[MAX], nextt[MAX], cnt = 0;
ll w[MAX], dis[MAX];
bool vis[MAX];
void add(ll a, ll b, ll c) {
u[cnt] = a, v[cnt] = b, w[cnt] = c;
nextt[cnt] = first[u[cnt]];
first[u[cnt]] = cnt; ++cnt;
}
void dijkstra() {
dis[1] = 0;
priority_queue<stu> list1;
list1.push({ 1,0 });
while (!list1.empty()) {
stu now = list1.top(); list1.pop();
if (vis[now.dot]) continue;
vis[now.dot] = true;
for (ll num = first[now.dot]; num != -1; num = nextt[num]) {
if (dis[v[num]] > dis[u[num]] + w[num]) {
dis[v[num]] = dis[u[num]] + w[num];
list1.push({ v[num],dis[v[num]] });
}
}
}
}
ll u1[MAX<<1], v1[MAX<<1], first1[MAX];
ll w1[MAX];
ll nextt1[MAX], cnt1 = 0;
ll deep[MAX];
ll s, t;
ll answer;
ll cur[MAX];
void add1(ll a, ll b, ll c) {
u1[cnt1] = a, v1[cnt1] = b, w1[cnt1] = c;
nextt1[cnt1] = first1[u1[cnt1]];
first1[u1[cnt1]] = cnt1; ++cnt1;
}
bool bfs() {
deque<ll> list1;
list1.push_back(s);
for(ll i=0;i<MAX;++i) deep[i]=INF;
deep[s] = 0;
memset(vis, false, sizeof(vis));
for (ll i = 1; i <= n; ++i) cur[i] = first1[i];
vis[s] = true;
while (!list1.empty()) {
ll now = list1.front(); list1.pop_front();
for (ll num = first1[now]; num != -1; num = nextt1[num]) {
if (!vis[v1[num]] && w1[num] > 0) {
vis[v1[num]] = true;
deep[v1[num]] = deep[now] + 1;
list1.push_back(v1[num]);
}
}
}
return deep[t] != INF;
}
ll dfs(ll now, ll limit) {
if (!limit || now == t) return limit;
ll flow = 0, length = 0;
for (ll num = first1[now]; num != -1; num = nextt1[num]) {
cur[now] = num;
if (deep[v1[num]] == deep[now] + 1 && (length = dfs(v1[num], min(limit, w1[num])))) {
flow += length;
w1[num] -= length;
w1[num ^ 1] += length;
limit -= length;
if (!limit) break;
}
}
return flow;
}
void dinic() {
while (bfs()){
answer += dfs(s, INF);
}
}
void solve() {
ll tt;
scanf("%lld", &tt);
while (tt--) {
cnt1 = 0;
scanf("%lld%lld", &n, &m);
cnt = 0;
memset(first, -1, sizeof(first));
memset(first1, -1, sizeof(first1));
memset(vis, false, sizeof(vis));
for(ll i=0;i<MAX;++i) dis[i]=INF;
memset(cur, 0, sizeof(cur));
for (ll i = 0; i < m; ++i) {
ll a, b;
ll c;
scanf("%lld%lld%lld", &a, &b, &c);
add(a, b, c);
}
dijkstra();
if(dis[n]==INF){
printf("0\n");
continue;
}
for (ll i = 1; i <= n; ++i)
for (ll num = first[i]; num != -1; num = nextt[num])
if (dis[v[num]] == dis[u[num]] + w[num])
add1(u[num], v[num], w[num]), add1(v[num], u[num], 0);
s = 1, t = n;
answer = 0;
dinic();
printf("%lld\n", answer);
}
}
int main(void)
{
solve();
return 0;
} hdu 6583
http://acm.hdu.edu.cn/showproblem.php?pid=6583
题意：
构造一个字符串，在字符串后面加上一个字符需要p代价，在字符串后面加上一个已有的字符子序列需要q代价。
做法：
考虑dp，
/*这题有个坑点就是一次性初始化会超时，所以就需要用哪个就初始化哪个*/
Code :
#include<bits/stdc++.h>
#define maxc 26
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
typedef long long ll;
int len[N * 2], //最长子串的长度(该节点字串数量=len[x]-len[link[x]])
link[N * 2], //后缀链接(最短串前部减少一个字符所到达的状态)
cnt[N * 2], //被后缀连接的数
nex[N * 2][maxc], //状态转移(尾部加一个字符的下一个状态)(图)
idx, //节点编号
last; //最后节点
ll epos[N * 2]; // enpos数（该状态子串出现数量）
char str[N];
ll a[N]; //长度为i的子串出现最大次数
/*
匹配字符串
*/
char s[N]; //用以匹配得字符串
int sum[N], ans[N]; //记录匹配字符串每个状态的匹配长度 ans 记录最终每个状态匹配的最短长度
int d[N], id[N];
void newnode(int l) {
len[idx] = l;
memset(nex[idx], 0, sizeof(nex[idx]));
}
void init() { //初始化
last = idx = 1; //1表示root起始点 空集
link[1] = len[1] = 0;
newnode(0);
}
//SAM建图
void insert(int c) { //插入字符，为字符ascll码值
int x = ++idx; //创建一个新节点x;
newnode(len[last] + 1); // 长度等于最后一个节点+1
epos[x] = 1; //接受节点子串除后缀连接还需加一
int p; //第一个有C转移的节点;
for (p = last; p && !nex[p][c]; p = link[p])
nex[p][c] = x;//沿着后缀连接 将所有没有字符c转移的节点直接指向新节点
if (!p)
link[x] = 1, cnt[1]++; //全部都没有c的转移 直接将新节点后缀连接到起点
else {
int q = nex[p][c]; //p通过c转移到的节点
if (len[p] + 1 == len[q]) //pq是连续的
link[x] = q, cnt[q]++; //将新节点后缀连接指向q即可,q节点的被后缀连接数+1
else {
int nq = ++idx; //不连续 需要复制一份q节点
len[nq] = len[p] + 1; //令nq与p连续
link[nq] = link[q]; //因后面link[q]改变此处 不加cnt
memcpy(nex[nq], nex[q], sizeof(nex[q])); //复制q的信息给nq
for (; p && nex[p][c] == q; p = link[p])
nex[p][c] = nq; //沿着后缀连接 将所有通过c转移为q的改为nq
link[q] = link[x] = nq; //将x和q后缀连接改为nq
cnt[nq] += 2; // nq增加两个后缀连接
}
}
last = x; //更新最后处理的节点
}
void GetNpos() { //求npos数，即该节点字串出现次数
queue<int>q;
for (int i = 1; i <= idx; i++)
if (!cnt[i])
q.push(i); //将所有没被后缀连接指向的节点入队
while (!q.empty()) {
int x = q.front();
q.pop();
epos[link[x]] += epos[x]; //子串数量等于所有后缀连接指向该节点的子串数量和+是否为接受节点
if (--cnt[link[x]] == 0)
q.push(link[x]); //当所有后缀连接指向该节点的处理完毕后再入队
}
}
void GetSubNum() { //求不相同字串数量
ll ans = 0;
for (int i = 2; i <= idx; i++)
ans += len[i] - len[link[i]]; //一状态子串数量等于len[i]-len[link[i]]
printf("%lld\n", ans);
}
void GetSubMax() { //求出所有长度为k的子串中出现次数最多的子串出现次数
GetNpos();
int n = strlen(str);
for (int i = 1; i <= idx; i++)
a[len[i]] = max(a[len[i]], epos[i]); //长度≤k的子串中出现次数最多的子串出现次数的最小值
for (int i = n - 1; i >= 1; i--)
a[i] = max(a[i], a[i + 1]); //求一遍后缀最大值就是答案
for (int i = 1; i <= n; i++)
printf("%lld\n", a[i]);
}
void Match()//匹配字符串得最长公共子串
{
for (int i = 1; i <= idx; i++)
ans[i] = len[i]; //初始匹配长度为本身字符串的子串长度
for (int i = 1; i <= idx; i++)
d[len[i]]++;
for (int i = 1; i <= idx; i++)
d[i] += d[i - 1];
for (int i = 1; i <= idx; i++)
id[d[len[i]]--] = i; /**/
while (~scanf("%s", s))
{
int n = strlen(s);
int num = 0, p = 1;// p代表节点 num 匹配长度
memset(sum, 0, sizeof(sum));
for (int i = 0; i < n; i++)
{
int c = s[i] - 'a';
if (nex[p][c])
num++, p = nex[p][c];
else
{
for (; p && !nex[p][c]; p = link[p]);
if (p)
num = len[p] + 1, p = nex[p][c];
else
num = 0, p = 1;
}
sum[p] = max(sum[p], num); /* 节点匹配最大长度*/
}
for (int i = idx; i >= 1; i--)/*与后缀链接相比*/
sum[link[id[i]]] = max(sum[link[id[i]]], sum[id[i]]);
for (int i = 1; i <= idx; i++)/**/
ans[i] = min(ans[i], sum[i]);
}
int Ans = 0; /**/
for (int i = 1; i <= idx; i++)
Ans = max(Ans, ans[i]);
printf("%d", Ans);
}
ll dp[N];
int main() {
int p, q;
while (~scanf("%s", str + 1))
{
init();
int n = strlen(str + 1);
scanf("%d %d", &p, &q);
int cur = 1, now = 1, pos = 1; /*cur 表示当前位置 now 表示 从now - cur的位置是匹配的*/
while (cur <= n)
{
int x = str[cur] - 'a';
if (nex[pos][x]) /*可以匹配*/
{
pos = nex[pos][x];
dp[cur] = min(dp[now - 1] + q, dp[cur - 1] + p);
cur++;
}
else if (cur == now) /*直接加入now位置的字符*/
{
insert(x);
dp[cur] = dp[cur - 1] + p;
cur++;
now++;
}
else/*如果前面的情况都不存在就需要把now位置字符加入并且调整开始匹配的位置*/
{
insert(str[now++] - 'a');
int tlen = cur - now;
for (; pos && link[pos] && len[link[pos]] >= tlen; pos = link[pos]);
}
}
printf("%lld\n", dp[n]);
}
}
/*
abcbc
*/ hdu 6586
http://acm.hdu.edu.cn/showproblem.php?pid=6586
题意:给你一个字符串,再给一个整数k,然后26行li,ri表示26个字母的限制范围,让你从给出的字符串中
找出字典序最小的k长度的字符串
------------------------------------------------
思路:贪心的搜,每次都选择符合条件的最小字母,搜满k个为止,
判断依据为选完当前位置后,剩下的字符串是否满足条件
Code :
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5+5;
char s[MAX],ans[MAX];
int n,l[30],r[30],len,used[30];
int index[30][MAX],endd[30],now[30],last,countt[MAX][30];
bool check=true;
void solve(){
while(~scanf("%s%d",s,&n)){
check=true;
last=-1;
memset(used,0,sizeof(used));
for(int i=0;i<26;++i) scanf("%d%d",&l[i],&r[i]);
memset(endd,-1,sizeof(endd));
memset(now,0,sizeof(now));
memset(countt,0,sizeof(countt));
len=strlen(s);
for(int i=0;i<len;++i){
int t = s[i]-'a';
index[t][++endd[t]]=i;
}
for(int i=len-1;i>=0;--i)
for(int j=0;j<26;++j)
countt[i][j]=countt[i+1][j]+(s[i]=='a'+j);
for(int i=0;i<n;++i){
bool low=false;
for(int j=0;j<26;++j){
bool flag=true;
//当前字母已经用到了上限
if(used[j]==r[j]) continue;
//取符合条件的那一个字母
while(now[j]<=endd[j]&&index[j][now[j]]<=last) ++now[j];
//当前字母已经用到了最后一个
if(now[j]>endd[j]) continue;
++used[j];
//check后面的字母是否能满足l,r数组
int tem=index[j][now[j]],sum=0;
for(int k=0;k<26;++k){
if(countt[tem+1][k]+used[k]<l[k]){
flag=0;
break;
}
sum+=max(l[k]-used[k],0);
}
if(sum>n-i-1) flag=0;
//check需要的字母是否能构成n长度字符串
sum=0;
for(int k=0;k<26;++k)
sum+=min(countt[tem+1][k],r[k]-used[k]);
if(sum<n-i-1) flag=0;
if(flag){
ans[i]='a'+j;
ans[i+1]='\0';
low=true;
last=tem;
break;
}
else --used[j];
}
if(!low){
check=false;
break;
}
}
if(check)printf("%s\n",ans);
else printf("-1\n");
}
}
int main(void)
{
solve();
return 0;
}
京公网安备 11010502036488号