ACM-ICPC 2018 徐州赛区网络预赛

 今天a了两道题，昨天爆零。菜~

•  A.Hard to prepare

  • 通过率: 28.66%
  • 通过人次: 570
  • 难度:

• B. BE, GE or NE

  • 通过率: 20.22%
  • 通过人次: 406
  • 难度:

•  C.Cacti Lottery

  • 通过率: 53.10%
  • 通过人次: 197
  • 难度:

•  D.Easy Math

  • 通过率: 10.22%
  • 通过人次: 118
  • 难度:

• E. End Fantasy VIX

  • 通过率: 20.28%
  • 通过人次: 44
  • 难度:

• F. Features Track

   代码1：

  • 通过率: 31.61%
  • 通过人次: 1159
  • 题意：有n帧，每个帧中都有k个特征，问：一个特征最多在几个帧中连续？
  • 题解：STL。做题的过程中倒是看明白题意，就是一直没有想到一个合适的数据结构来存储。
    很简单的一道题。
    其实用map<pair<int,int>,pair<int,int> >mp;这个结构能够完全存储。mp[make_pair(x,y).first存储特征x,y在连续帧中出现的次数，mp[make_pair(x,y).second表示上次出现在哪个帧当中。
  • mp[make_pair(x,y).second和mp[pair<int,int> (x,y)]值相等，我想应该是等价的吧。

  • #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<map>
    using namespace std;
    map<pair<int,int>,pair<int,int> >mp;int main(){int t,n,k,x,y,ans;scanf("%d",&t);while(t--){mp.clear();ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&k);while(k--){scanf("%d%d",&x,&y);//printf("%d****%d\n",mp[make_pair(x,y)].first,mp[make_pair(x,y)].second);if(mp[make_pair(x,y)].second==i) continue;if(mp[make_pair(x,y)].first==0||mp[make_pair(x,y)].second==i-1){mp[make_pair(x,y)].first++;}else{mp[make_pair(x,y)].first=1;}	mp[make_pair(x,y)].second=i;ans=max(ans,mp[make_pair(x,y)].first);}}printf("%d\n",ans);}return 0;
    }

    代码2：

  • #include<bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> pair_int;
    #define mp make_pair
    map<pair_int,pair_int> m;int main(){int t;scanf("%d",&t);while(t--){int n;int x,y,res=0;scanf("%d",&n);for(int i=1;i<=n;i++){int k;scanf("%d",&k);for(int j=1;j<=k;j++){scanf("%d%d",&x,&y);if(m.count(mp(x,y))){if(m[mp(x,y)].second==i) continue;if(m[mp(x,y)].second==i-1){m[mp(x,y)].first++;m[mp(x,y)].second=i;res=max(m[mp(x,y)].first,res);}else{m[mp(x,y)].first=1;m[mp(x,y)].second=i;}}else{m.insert(mp(mp(x,y),mp(1,i)));res=max(1,res);}}}m.clear();printf("%d\n",res);}return 0;
    }

     

• I. Trace

  • 通过率: 30.59%
  • 通过人次: 721
  • 难度:

•  G.Ryuji doesn't want to study （比赛过程中做出的题目）

  • 通过率: 24.32%
  • 通过人次: 1140
  • 题意：线段树的区间求和，单点更新。
  • 题解：线段树。当然这个题，我的想法是用两棵线段树来维护，一个维护数组a[i]，一个用来维护（n-i+1）*a[i].

  • #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    #define maxn 100010
    #define inf 0x3f3f3f3fstruct Tree{ll left,right;  //区间的端点ll sum;   //视题目要求而定
    }tree[maxn<<2],tree1[maxn<<2];
    ll a[maxn],b[maxn];void pushup(ll id){tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
    }void pushup1(ll id){tree1[id].sum=tree1[id<<1].sum+tree1[id<<1|1].sum;
    }void build(ll id,ll l,ll r){  //构造线段树tree[id].left=l,tree[id].right=r;if(l==r){  //叶节点，直接更新mx[i]tree[id].sum=a[r];return;}int mid=(tree[id].left+tree[id].right)>>1;build(id<<1,l,mid); //递归更新左子树build(id<<1|1,mid+1,r);  //递归更新右子树pushup(id);  //递归的过程，就是自底向上更新mx[i]的过程，在纸上模拟下就能体会到
    }void build1(ll id,ll l,ll r){  //构造线段树tree1[id].left=l,tree1[id].right=r;if(l==r){  //叶节点，直接更新mx[i]tree1[id].sum=b[r];return;}int mid=(tree1[id].left+tree1[id].right)>>1;build1(id<<1,l,mid); //递归更新左子树build1(id<<1|1,mid+1,r);  //递归更新右子树pushup1(id);  //递归的过程，就是自底向上更新mx[i]的过程，在纸上模拟下就能体会到
    }void update(ll id,ll pos,ll val){ //更新某个点的信息，并维护相关点的信息if(tree[id].left==tree[id].right){  //对应的叶节点直接更新tree[id].sum=val;return ;}int mid=(tree[id].left+tree[id].right)>>1;if(pos<=mid) update(id<<1,pos,val);else update(id<<1|1,pos,val);pushup(id);  //递归的过程，就是自底向上更新mx[i]的过程，在纸上模拟下就能体会到
    }void update1(ll id,ll pos,ll val){ //更新某个点的信息，并维护相关点的信息if(tree1[id].left==tree1[id].right){  //对应的叶节点直接更新tree1[id].sum=val;return ;}int mid=(tree1[id].left+tree1[id].right)>>1;if(pos<=mid) update1(id<<1,pos,val);else update1(id<<1|1,pos,val);pushup1(id);  //递归的过程，就是自底向上更新mx[i]的过程，在纸上模拟下就能体会到
    }ll query(ll id,ll l,ll r){  //查询[l,r]中的最大值if(tree[id].left==l&&tree[id].right==r){ //当前结点完全包含在查询区间内return tree[id].sum;}int mid=(tree[id].left+tree[id].right)>>1;//cout<<"mid="<<mid<<endl;if(r<=mid) return query(id<<1,l,r);  //往左走else if(mid<l) return query(id<<1|1,l,r);   //往右走else return query(id<<1,l,mid)+query(id<<1|1,mid+1,r);
    }ll query1(ll id,ll l,ll r){  //查询[l,r]中的最大值if(tree1[id].left==l&&tree1[id].right==r){ //当前结点完全包含在查询区间内return tree1[id].sum;}int mid=(tree1[id].left+tree1[id].right)>>1;//cout<<"mid="<<mid<<endl;if(r<=mid) return query1(id<<1,l,r);  //往左走else if(mid<l) return query1(id<<1|1,l,r);   //往右走else return query1(id<<1,l,mid)+query1(id<<1|1,mid+1,r);
    }int main()
    {ll n,m;ll u,v;scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);b[i]=a[i]*(n-i+1);}ll q;build(1,1,n);build1(1,1,n);while(m--){scanf("%lld%lld%lld",&q,&u,&v);if(q==1){printf("%lld\n",query1(1,u,v)-(n-v)*query(1,u,v));// printf("%lld******%lld\n",query(1,u,v),query1(1,u,v));}else{update(1,u,v);v=(n-u+1)*v;update1(1,u,v);}}return 0;
    }

     

•  K.Characters with Hash （比赛过程做出的）

  • 通过率: 26.21%
  • 通过人次: 1663
  • 题意：输入一个字符作为seed，再输入一个字符串s，遍历字符串s，
  • 题解：模拟。这题通过率还可以，上来就看这道题了。按照题目中的规则进行字符串的转化，输出答案的长度。注意不算前导零。当时就是没有想到：当答案为0时，输出1.一直wa~

  • #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    int main(){std::ios::sync_with_stdio(false);int t;string a;int n;ll cnt;char ch;cin>>t;while(t--){cin>>n>>ch;if(n<=0){cout<<"0"<<endl;continue;}ll m;cin>>a;cnt=0;for(int i=0;i<n;i++){m=abs(ch-a[i]);if(m==0&&cnt==0) continue;if(cnt==0&&m<10) cnt++;else cnt+=2;}if(cnt==0) cnt=1;cout<<cnt<<endl;}return 0;
    }

     

• L. Maze Designer

  • 通过率: 29.04%
  • 通过人次: 266
  • 难度:

•  M.Morgana Net

  • 通过率: 14.98%
  • 通过人次: 114
  • 难度: