2017年 乌鲁木齐 网络赛
2018-09-25 本文已影响10人
_弓长_大人
乌鲁木齐 网络赛 字符串 匹配 修改 查询
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+5;
string s[N];
int bit[N];
int m;
char str1[N];
inline int lowbit(int x)
{
return x&-x;
}
inline void add(int i,int x)
{
while(i<=m)
bit[i]+=x,i+=lowbit(i);
}
inline int sum(int x)
{
int res=0;
while(x)
res+=bit[x],x-=lowbit(x);
return res;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
scanf("%s",str1);
string str(str1);
char tmp[50];
scanf("%s",tmp);
string ss(tmp);
int len=ss.size();
memset(bit,0,sizeof(bit));
m=str.size()-len+1;
for(int i=0;i<str.size()-len+1;i++)
{
for(int j=0;j<len;j++)
s[i+1]+=str[i+j];
if(s[i+1]==ss)
add(i+1,1);
}
while(n--)
{
char c[2];
int l,r;
char x[2];
scanf("%s",c);
if(c[0]=='C')
{
scanf("%d",&l);
scanf("%s",x);
for(int i=max(l-len+1,1);i<=l;i++)
{
string pre=s[i];
s[i][l-i]=x[0];
if(pre==ss&&s[i]!=ss)
add(i,-1);
else if(pre!=ss&&s[i]==ss)
add(i,1);
}
}
else
{
scanf("%d%d",&l,&r);
if(l>r)
swap(l,r);
int x=r-len+1;
int ans;
if(x<l)
ans=0;
else
ans=sum(x)-sum(l-1);
printf("%d\n",ans);
}
}
for(int i=0;i<str.size()-len+1;i++)
s[i+1].clear();
puts("");
}
return 0;
}
J题 途经一点 两点 最短距离
#include <bits/stdc++.h>
#define INF 1000000007
#define FI first
#define SE second
#define PB push_back
#define VI vector<int>
#define MP make_pair
#define SZ(x) int((x).size())
#define FOR(x, st, ed) for(auto x = (st); x < (ed); ++x)
#define FORE(x, st, ed) for(auto x = (st); x <= (ed); ++x)
#define CLR(arr, val) memset(arr, val, sizeof(arr))
#define INFO(tag, st, ed, x) printf("%s: ", tag); \
FOR(_i, st, ed) cout << x[_i] << ' '; puts("");
#ifdef ACM_TEST
#define LOG printf
#else
#define LOG(...)
#endif // ACM_TEST
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
const int NUM = 100010;
const int MAXV = 1e5 + 10, MAXE = MAXV * 4;
struct edge {int next, to, cap, cost;} e[MAXE];
int head[MAXV], E;
void gInit() {memset(head, -1, sizeof(head)); E = 0;}
void add_edge(int u, int v, int cap, int cost) {
// LOG("add edge: %d-->%d: cap = %d, cost = %d\n", u, v, cap, cost);
e[E] = {head[u], v, cap, cost}; head[u] = E++;
e[E] = {head[v], u, 0, -cost}; head[v] = E++;
}
int dist[MAXV];
int InQue[MAXV], Pree[MAXV], Prev[MAXV];
bool spfa(int s, int t) {
memset(dist, 0x3f, sizeof(dist));
// memset(InQue, 0, sizeof(InQue));
queue<int> que;
que.push(s);
InQue[s] = 1;
dist[s] = 0;
while (!que.empty()) {
int u = que.front(); que.pop();
InQue[u] = 0;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to;
if (e[i].cap > 0 && dist[v] > dist[u] + e[i].cost) {
dist[v] = dist[u] + e[i].cost;
Pree[v] = i;
Prev[v] = u;
if (InQue[v] == 0) {
InQue[v] = 1;
que.push(v);
}
}
}
}
return dist[t] != 0x3f3f3f3f;
}
int min_cost_flow(int s, int t, int flow) {
int ans = 0;
while (flow > 0 && spfa(s, t)) {
int cur_flow = flow;
for (int u = t; u != s; u = Prev[u]) {
cur_flow = min(cur_flow, e[Pree[u]].cap);
}
flow -= cur_flow;
ans += dist[t] * cur_flow;
for (int u = t; u != s; u = Prev[u]) {
e[Pree[u]].cap -= cur_flow;
e[Pree[u] ^ 1].cap += cur_flow;
}
}
if (flow) return -1;
return ans;
}
int main() {
#ifdef ACM_TEST
freopen("in.txt", "r", stdin);
#else
std::ios::sync_with_stdio(false);
cin.tie(0);
#endif
int T;
cin >> T;
while (T--) {
int m;
cin >> m;
map<string, int> id;
gInit();
int V = 0;
id["Dalian"] = V;
add_edge(V, V + 1, 1, 0);
// add_edge(V + 1, V, 1, 0);
V += 2;
id["Xian"] = V;
add_edge(V, V + 1, 1, 0);
// add_edge(V + 1, V, 1, 0);
V += 2;
id["Shanghai"] = V;
add_edge(V, V + 1, 2, 0);
// add_edge(V + 1, V, 1, 0);
V += 2;
string from, to;
int dis;
for (int i = 0; i < m; ++i) {
cin >> from >> to >> dis;
if (id.count(from) == 0) {
id[from] = V;
add_edge(V, V + 1, 1, 0);
// add_edge(V + 1, V, 1, 0);
V += 2;
}
if (id.count(to) == 0) {
id[to] = V;
add_edge(V, V + 1, 1, 0);
// add_edge(V + 1, V, 1, 0);
V += 2;
}
add_edge(id[from] + 1, id[to], 1, dis);
add_edge(id[to] + 1, id[from], 1, dis);
}
int src = V, sink = V + 1;
add_edge(src, id["Dalian"], 1, 0);
add_edge(src, id["Xian"], 1, 0);
add_edge(id["Shanghai"] + 1, sink, 2, 0);
cout << min_cost_flow(src, sink, 2) << '\n';
}
return 0;
}
有向图 两点 最长
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 100005
typedef long long ll;
int len[10005];
bool vis[100005];
int n,m;
struct Node
{
int v,u;
int id;
};
Node node[MAX];
int head[MAX];
int cnt=0;
int top=0;
int a,b;
int c;
int ans=0;
void init()
{
memset(head,-1,sizeof(head));
memset(len,0,sizeof(len));
memset(vis,0,sizeof(vis));
cnt=0;
top=0;
}
void add_e(int u,int v,int id)
{
node[cnt].v=v;
node[cnt].u=head[u];
node[cnt].id=id;
head[u]=cnt++;
}
int dfs(int j)
{
for(int i=head[j];i!=-1;i=node[i].u)
{
if(!vis[i])
{
vis[i]=true;
len[j]=max(node[i].id+dfs(node[i].v),len[j]);
}
}
ans=max(len[j],ans);
return len[j];
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
init();
ans=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add_e(a,b,c);
}
for(int i=1;i<=n;i++)
{
dfs(i);
}
printf("%d\n",ans);
}
return 0;
}
