2021-杭电-4-持久更新记录

2
1sinx+0cosx+3x+6/sinx
0

NO
YES

int main() {
  string s;
  int _ = read;
  while(_ --){
    cin >> s;
    int len = s.size(),flag = 0;
    for(int i=0;i<len;i++) if(isdigit(s[i]) && s[i] != '0' && !flag) flag = 1;
    if(!flag) puts("YES");
    else puts("NO");
  }
  return 0;
}

Case #1:
5 19
24 32
40 41
50 58
63 70
76 84
89 97

#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
char s[33][103];
bool check(int x){
    for(int i=1;i<=30;i++) if(s[i][x] == '#') return true;
    return false;
}
int main(){
    int _; cin >> _;
    for(int I = 1;I <= _;I ++){
        printf("Case #%d:\n",I);
        for(int i=1;i<=30;i++) scanf("%s",s[i]+1),s[i][0] = s[i][101] = '.';
        stack<PII> st;
        int l = 0,r = 0,cnt = 0;
        for(int i=100;i>=1;i--){
            if(check(i) && !check(i+1)) {
                r = i;
                if(cnt == 6) break;
            }
            if(check(i) && !check(i-1)) {
                l = i;
                ++ cnt;
                st.push({l,r});
            }
        }
        for(int i=1;i<=100;i++){
            if(check(i) && !check(i-1)) {
                l = i;
                break;
            }
        }
        st.push({l,r});
        while(st.size()){
            printf("%d %d\n",st.top().first,st.top().second);
            st.pop();
        }
    }
    return 0;
}

1
6
1 1 2 2 3
1 1 4 5 1 4

495644981 518101442
495644981 518101442
397599492 896634980
612255048 326063507
495644981 518101442
397599492 896634980

#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
const int x = 19560929;
int idx = 0,head[maxn],ct;
ll a1[maxn],a2[maxn],cnt[maxn],a[2007][2007],w[maxn];
inline ll qPow(ll a,ll b,ll k){
    ll res = 0;
    while(b){
        if(b&1) res = (res + a) % k;
        b >>= 1;
        a = (a + a) % k;
    }
    return res;
}
struct node{
    int v,nex;
}e[maxn];
void init(){
    for(int i=0;i<maxn;i++) head[i] = -1;
    idx = 0;
}
void dfs(int u,int fa,int rt){
    for(int i=head[u];~i;i=e[i].nex){
        int to = e[i].v;
        if(to == fa) continue;
        if(cnt[w[to]] == 0) ++ ct;
        ++ cnt[w[to]];
        a[rt][to] = ct;
        dfs(to,u,rt);
        -- cnt[w[to]];
        if(cnt[w[to]] == 0) -- ct;
    }
}
void add(int u,int v){
    e[idx].v = v;
    e[idx].nex = head[u];
    head[u] = idx++;
}
int main(){
    a1[1] = a2[1] = 1;
    for(int i=2;i<=2000;i++) a1[i] = qPow(a1[i-1],x,mod),a2[i] = qPow(a2[i-1],x,mod+2);
    int _; cin >> _;
    while(_ --){
        init();
        memset(cnt,0,sizeof cnt);
        int n;
        scanf("%d",&n);
        for(int i=2;i<=n;i++){
            int v;scanf("%d",&v);
            add(i,v);
            add(v,i);
        }
        for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
        for(int i=1;i<=n;i++){
            ct = 1;
            ++ cnt[w[i]];
            a[i][i] = 1;
            dfs(i,0,i);
            -- cnt[w[i]];
        }
        for(int i=1;i<=n;i++){
            ll c1 = 0,c2 = 0;
            for(int j=1;j<=n;j++){
                c1 = (c1 + a[i][j] * a1[j] % mod) % mod;
                c2 = (c2 + a[i][j] * a2[j] % (mod + 2)) % (mod + 2);
            }
            printf("%lld %lld\n",c1,c2);
        }
    }
    return 0;
}

1
4 4 4
1 3
3 4
3 2
4 3

10

#define PI (double)acos(-1.0)
#define debug(x) cout<<#x<<" :"<<x<<endl
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mid ((l+r)>>1)
struct SegmentTree{
  struct node{
    int l,r,len,sum,lazy;
  }tree[maxn << 2];
  void Pushup(int rt){
    tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
  }
  void Pushdown(int rt){
    if(tree[rt].lazy != -1) {
      int lz = tree[rt].lazy;
      tree[rt].lazy = -1;
      tree[rt<<1].lazy = tree[rt<<1|1].lazy = lz;
      tree[rt<<1].sum = tree[rt<<1].len * lz;
      tree[rt<<1|1].sum = tree[rt<<1|1].len * lz;
    }
  }
  void Build(int rt,int l,int r){
    tree[rt] = {l,r,r-l+1,0,-1};
    if(l == r) return ;
    Build(rt<<1,l,mid);
    Build(rt<<1|1,mid+1,r);
  }
  void Update(int rt,int l,int r,int x){
    if(tree[rt].l > r || tree[rt].r < l) return ;
    if(tree[rt].l >= l && tree[rt].r <= r) {
      tree[rt].lazy = x;
      tree[rt].sum = tree[rt].len * x;
      return ;
    }
    Pushdown(rt);
    Update(rt<<1,l,r,x);
    Update(rt<<1|1,l,r,x);
    Pushup(rt);
  }
  int QuerySum(int rt,int l,int r){
    if(tree[rt].l > r || tree[rt].r < l) return 0;
    if(tree[rt].l >= l && tree[rt].r <= r) return tree[rt].sum;
    Pushdown(rt);
    return QuerySum(rt<<1,l,r) + QuerySum(rt<<1|1,l,r);
  }
  int Query(int rt,int l,int r){
    if(l > r || QuerySum(rt,l,r) == 0) return -1;
    if(tree[rt].l == tree[rt].r) return tree[rt].l;
    Pushdown(rt);
    int lval = QuerySum(rt<<1,l,r);
    int rval = QuerySum(rt<<1|1,l,r);
    if(lval) return Query(rt<<1,l,r);
    else return Query(rt<<1|1,l,r);
  }
}T[2];
vector<int> vet[maxn];
int main() {
  int _ = read;
  while(_ --){
    int n = read,m = read,k = read;
    for(int i=1;i<=m;i++) vet[i].clear(),vet[i].push_back(0);
    while(k --){
      int x = read,y = read;
      vet[y].push_back(x);
    }
    ll ans = 0;
    T[0].Build(1,1,n);
    T[1].Build(1,1,n);
    sort(vet[1].begin(),vet[1].end());
    if(vet[1].size() >= 2) T[1].Update(1,1,vet[1][1]-1,1);
    else T[1].Update(1,1,n,1);
    ans += T[1].tree[1].sum;
    for(int i=2;i<=m;i++){
      int cur = i&1,pre = cur^1;
      T[cur].Update(1,1,n,1);
      int siz = vet[i].size();  
      for(int j=0;j<siz;j++){
        int at = vet[i][j];
        int val = T[pre].Query(1,at+1,n);
        if(val == -1) T[cur].Update(1,at,n,0);
        else T[cur].Update(1,at,val-1,0);
      }
      ans += T[cur].tree[1].sum;
    }
    printf("%lld\n",ans);
  }
  return 0;
}