1002. Ch’s gift
首先考虑序列上的问题。
考虑到
再搬到树上,直接套一个树链剖分就行了,树状数组就能维护。
- #include <bits/stdc++.h>
- using namespace std;
-
- typedef long long ll;
- const int MAXN=1e5+5;
- struct Edge {
- int to,next;
- } edge[MAXN*2];
- int head[MAXN],tot;
- int top[MAXN],fa[MAXN];//父亲节点
- int deep[MAXN];//深度
- int num[MAXN];//num[v] 表示以v为根的子树的节点数
- int p[MAXN];//p[v]表示v对应的位置
- int fp[MAXN];//fp和p数组相反
- int son[MAXN];//重儿子
- int pos;
- int v[MAXN*3];
-
- void init()
- {
- tot = 0;
- memset(head,-1,sizeof(head));
- pos = 1;
- memset(son,sizeof(son));
- }
-
- void addedge(int u,int v)
- {
- edge[tot].to = v;
- edge[tot].next = head[u];
- head[u] = tot++;
- }
-
- void dfs1(int u,int pre,int d)
- {
- deep[u] = d;
- fa[u] = pre;
- num[u] = 1;
- for(int i = head[u]; i != -1; i = edge[i].next) {
- int v = edge[i].to;
- if(v != pre) {
- dfs1(v,u,d+1);
- num[u] += num[v];
- if(son[u] == -1 || num[v] > num[son[u]])
- son[u] = v;
- }
- }
- }
-
- void getpos(int u,int sp)
- {
- top[u] = sp;
- p[u] = pos++;
- fp[p[u]] = u;
- if(son[u] == -1) return;
- getpos(son[u],sp);
- for(int i = head[u]; i != -1; i = edge[i].next) {
- int v = edge[i].to;
- if( v != son[u] && v != fa[u])
- getpos(v,v);
- }
- }
-
- inline int lowbit(int x)
- {
- return x&(-x);
- }
-
- ll c[MAXN];
- ll sum(int i)
- {
- ll s = 0;
- while(i > 0) {
- s += c[i];
- i -= lowbit(i);
- }
- return s;
- }
-
- void add(int i,int val)
- {
- while(i <MAXN) {
- c[i] += val;
- i += lowbit(i);
- }
- }
-
- ll query(int u,int v)
- {
- int f1 = top[u],f2 = top[v];
- ll res=0;
- while(f1 != f2) {
- if(deep[f1] < deep[f2]) {
- swap(f1,f2);
- swap(u,v);
- }
- res+=sum(p[u])-sum(p[f1]-1);
- u = fa[f1];
- f1 = top[u];
- }
- if(deep[u] > deep[v]) swap(u,v);
- res+=sum(p[v])-sum(p[u]-1);
- return res;
- }
-
- struct Query {
- int u,v,val,zf,id;
- bool operator <(const Query &R) {
- return val<R.val;
- }
- } q[MAXN*2];
- int a[MAXN];
- struct Node {
- int iv,id;
- bool operator <(const Node &R) {
- return iv<R.iv;
- }
- } ia[MAXN];
- ll ans[MAXN];
-
- int main()
- {
- int n,m;
- while (scanf("%d%d",&n,&m)!=EOF) {
- init();
- int vtot=0;
- for (int i=1;i<=n;i++) {
- scanf("%d",&a[i]);
- v[++vtot]=a[i];
- }
- for (int i=1;i<n;i++) {
- int x,y;
- scanf("%d%d",&x,&y);
- addedge(x,y);
- addedge(y,x);
- }
- dfs1(1,0,0);
- getpos(1,1);
- for (int i=1;i<=m;i++) {
- int s,t,b;
- scanf("%d%d%d%d",&s,&t,&a,&b);
- q[i+i-1]={s,a-1,i};
- q[i+i]={s,b,1,i};
- v[++vtot]=a-1;
- v[++vtot]=b;
- }
- m<<=1;
- sort(v+1,v+vtot+1);
- vtot=unique(v+1,v+vtot+1)-v-1;
- for (int i=1;i<=m;i++) {
- q[i].val=lower_bound(v+1,v+vtot+1,q[i].val)-v;
- }
- for (int i=1;i<=n;i++) {
- ia[i].iv=lower_bound(v+1,a[i])-v;
- ia[i].id=i;
- }
- sort(q+1,q+1+m);
- sort(ia+1,ia+n+1);
- memset(ans,sizeof(ans));
- int j=1;
- for (int i=1;i<=m;i++) {
- while (j<=n&&ia[j].iv<=q[i].val) {
- add(p[ia[j].id],a[ia[j].id]);
- ++j;
- }
- ans[q[i].id]+=q[i].zf*query(q[i].u,q[i].v);
- }
- m>>=1;
- for (int i=1;i<=m;i++) {
- printf("%lld%c",ans[i]," \n"[i==m]);
- }
- }
- return 0;
- }
ps: 可持久化线段树可以在线回答,等写出来了更新
1005. FFF at Valentine
强连通缩点加拓扑序判分叉,不多说了。
- #include <bits/stdc++.h>
- using namespace std;
-
- const int MAXN = 1010;//点数
- const int MAXM = 50010;//边数
- struct Edge {
- int fr,to,next;
- } eg[MAXM];
- int head[MAXN],tot;
- int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc
- int Index,top;
- int scc;//强连通分量的个数
- bool Instack[MAXN];
- int T,n,m;
- bool g[MAXN][MAXN];
- int in[MAXN];
- vector<int> G[MAXN];
-
- void Tarjan(int u)
- {
- int v;
- Low[u] = DFN[u] = ++Index;
- Stack[top++] = u;
- Instack[u] = true;
- for(int i = head[u]; i != -1; i = eg[i].next) {
- v = eg[i].to;
- if( !DFN[v] ) {
- Tarjan(v);
- if( Low[u] > Low[v] )Low[u] = Low[v];
- } else if(Instack[v] && Low[u] > DFN[v])
- Low[u] = DFN[v];
- }
- if(Low[u] == DFN[u]) {
- scc++;
- do {
- v = Stack[--top];
- Instack[v] = false;
- Belong[v] = scc;
- } while( v != u);
- }
- }
-
- void solve(int N)
- {
- memset(DFN,sizeof(DFN));
- memset(Instack,false,sizeof(Instack));
- Index = scc = top = 0;
- for(int i = 1; i <= N; i++)
- if(!DFN[i])
- Tarjan(i);
- }
-
- void init()
- {
- tot = 0;
- memset(head,sizeof(head));
- }
-
- bool bad()
- {
- queue<int> Q;
- for (int i=1;i<=scc;i++) {
- if (!in[i]) {
- Q.push(i);
- }
- }
- while (!Q.empty()) {
- if (Q.size()>1) {
- return true;
- }
- int u=Q.front();
- Q.pop();
- for (int v:G[u]) {
- if (--in[v]==0) {
- Q.push(v);
- }
- }
- }
- return false;
- }
-
- int main()
- {
- scanf("%d",&T);
- while (T--) {
- scanf("%d%d",&m);
- init();
- for (int i=1;i<=m;i++) {
- int x,y;
- scanf("%d%d",&x,&y);
- eg[tot]={x,head[x]};
- head[x]=tot++;
- }
- solve(n);
- memset(g,sizeof(g));
- memset(in,sizeof(in));
- for (int i=1;i<=scc;i++) {
- G[i].clear();
- }
- for (int i=0;i<m;i++) {
- int x=Belong[eg[i].fr];
- int y=Belong[eg[i].to];
- if (x!=y) {
- if (!g[x][y]) {
- g[x][y]=1;
- G[x].push_back(y);
- in[y]++;
- }
- }
- }
- if (bad()) {
- puts("Light my fire!");
- } else {
- puts("I love you my love and our love save us!");
- }
- }
- return 0;
- }
1006. Senior Pan
这题主要是题意有点不清楚。。。大小为
拆点,加超级源超级汇,再跑一下dij 。这个限制可以每个点维护一下被谁松弛过,比如现在想用
- #include <bits/stdc++.h>
- using namespace std;
-
- typedef long long ll;
- typedef pair<ll,int> PLI;
- const int N=100010;
- struct Edge {
- int go,next;
- } eg[N*5];
- int last[N<<1],tot;
- ll d[N<<1];
- int vis[N<<1],st[N];
- set<int> re[N<<1];
- int T,m,k,cas=0;
-
- namespace fastIO {
- #define BUF_SIZE 100000
- //fread -> read
- bool IOerror = 0;
- inline char nc() {
- static char buf[BUF_SIZE],*p1 = buf + BUF_SIZE,*pend = buf + BUF_SIZE;
- if(p1 == pend) {
- p1 = buf;
- pend = buf + fread(buf,BUF_SIZE,stdin);
- if(pend == p1) {
- IOerror = 1;
- return -1;
- }
- }
- return *p1++;
- }
- inline bool blank(char ch) {
- return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
- }
- inline void read(int &x) {
- char ch;
- while(blank(ch = nc()));
- if(IOerror)
- return;
- for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
- }
- #undef BUF_SIZE
- };
-
- void dij(int S)
- {
- priority_queue< PLI,vector<PLI>,greater<PLI> > q;
- memset(d,0x3f,sizeof(d));
- memset(vis,sizeof(vis));
- d[S]=0; q.push(PLI(d[S],S));
- while (!q.empty()){
- PLI tmp=q.top();
- q.pop();
- int u=tmp.second;
- if (vis[u]) continue;
- vis[u]=1;
- for (int i=last[u];i!=-1;i=eg[i].next) {
- int &v=eg[i].go;
- // printf("%d %d\n",v);
- if (u<=n&&v>n&&st[v-n]) {
- if (re[u+n].find(v-n)!=re[u+n].end()) continue;
- }
- if (d[v]>d[u]+eg[i].val) {
- re[v].insert(u);
- d[v]=d[u]+eg[i].val;
- q.push(PLI(d[v],v));
- }
- }
- }
- }
-
- void addedge(int x,int y,int z)
- {
- eg[tot]={y,z,last[x]};
- last[x]=tot++;
- }
-
- int main()
- {
- fastIO::read(T);
- while (T--) {
- fastIO::read(n);
- fastIO::read(m);
- tot=0;
- memset(last,sizeof(last));
- for (int i=1;i<=m;i++) {
- int x,z;
- fastIO::read(x);
- fastIO::read(y);
- fastIO::read(z);
- addedge(x,n+y,z);
- }
- fastIO::read(k);
- memset(st,sizeof(st));
- int S=0,T=n+n+1;
- for (int i=1;i<=k;i++) {
- int x;
- fastIO::read(x);
- st[x]=1;
- addedge(S,x,0);
- addedge(n+x,T,0);
- }
- for (int i=1;i<=n;i++) {
- addedge(n+i,i,0);
- }
- for (int i=0;i<=n+n+1;i++) {
- re[i].clear();
- }
- dij(S);
- printf("Case #%d: %lld\n",++cas,d[T]);
- }
- return 0;
- }
1008. Numbers
从小到大取,
- #include <bits/stdc++.h>
- using namespace std;
-
- const int M=125260;
- int a[M];
- multiset<int> ss;
-
- namespace fastIO {
- #define BUF_SIZE 100000
- //fread -> read
- bool IOerror = 0;
- inline char nc() {
- static char buf[BUF_SIZE],stdin);
- if(pend == p1) {
- IOerror = 1;
- return -1;
- }
- }
- return *p1++;
- }
- inline bool blank(char ch) {
- return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
- }
- inline void read(int &x) {
- char ch;
- while(blank(ch = nc()));
- if(IOerror)
- return;
- for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
- }
- #undef BUF_SIZE
- };
-
- int main()
- {
- int m,x;
- while (fastIO::read(m),!fastIO::IOerror) {
- for (int i=1;i<=m;i++) {
- fastIO::read(x);
- ss.insert(x);
- }
- int n=0;
- a[++n]=*ss.begin();
- ss.erase(ss.begin());
- while (!ss.empty()) {
- a[++n]=*ss.begin();
- ss.erase(ss.begin());
- for (int i=1;i<n;i++) {
- ss.erase(ss.find(a[i]+a[n]));
- }
- }
- printf("%d\n",n);
- for (int i=1;i<=n;i++) {
- printf("%d%c",a[i]," \n"[i==n]);
- }
- }
- return 0;
- }
1010. Two strings
主要还是题意比较坑。。。匹配.*
是要把.
先变成某个字符再处理*
。。。
队友(wenwenla)写了一种dp,先预处理pattern,dp[i]保存pattern前i个字符为止可以匹配到text的最左和最右,可以证明这个界里面的每一个都是可取的。
具体实现加一维表示最左最右,然后发现第一维可以去掉。
- #include <bits/stdc++.h>
- using namespace std;
-
- const int N=2510,INF=1<<30;
- char a[N],b[N];
- int dp[2];
- bool mul[N];
-
- int main()
- {
- int T;
- scanf("%d",&T);
- while (T--) {
- scanf("%s",a+1);
- scanf("%s",b+1);
- int la=strlen(a+1);
- int lb=strlen(b+1);
- int j=0;
- memset(mul,sizeof(mul));
- for (int i=1;i<=lb;i++) {
- if (b[i]=='*') {
- mul[j]=1;
- } else {
- b[++j]=b[i];
- }
- }
- lb=j;
- int flag=0;
- dp[0]=dp[1]=0;
- for (int i=1;i<=lb;i++) {
- if (mul[i]) {
- int p=dp[1];
- if (p<la&&(b[i]=='.'||b[i]==a[p+1])) {
- ++p;
- while (p<la&&a[p+1]==a[p]) p++;
- }
- dp[1]=p;
- } else {
- int ll=INF,rr=-INF;
- for (int j=dp[0]+1;j<=dp[1]+1;j++) {
- if (j>la) break;
- if (b[i]=='.'||b[i]==a[j]) {
- ll=min(ll,j);
- rr=max(rr,j);
- }
- }
- if (ll==INF) {
- flag=1;
- break;
- }
- dp[0]=ll;dp[1]=rr;
- }
- }
- if (flag||dp[1]!=la) {
- puts("no");
- } else {
- puts("yes");
- }
- }
- return 0;
- }
时间0ms,就是容易写错。。。比赛的时候前面WA的都交上去了,最后一次AC的代码却没交上去[cry]。。。而且我们亲眼看到点了submit以后页面跳转了。。。结果连提交记录都没有??
后来有人说了才发现这样直接正则就能过,这题出得真好??
- #include <bits/stdc++.h>
- using namespace std;
-
- const char sp[]="(q*|w*|e*|r*|t*|y*|u*|i*|o*|p*|a*|s*|d*|f*|g*|h*|j*|k*|l*|z*|x*|c*|v*|b*|n*|m*)";
-
- int main() {
- int T;
- scanf("%d",&T);
- scanf("\n");
- while(T--) {
- string a,c;
- getline(cin,a);
- getline(cin,b);
- for (int i=0;i<b.length();i++) {
- if (i<b.length()-1&&b[i]=='.'&&b[i+1]=='*') {
- c+=sp;i++;
- } else {
- c+=b[i];
- }
- }
- auto re = regex(c);
- if(regex_match(a,re)) {
- puts("yes");
- } else {
- puts("no");
- }
- }
- return 0;
- }