CCF-CSP真题《202209-4—吉祥物投票》思路+python题解

偏执的太偏执、 2023-09-27 12:12 39阅读 0赞

> 想查看其他题的真题及题解的同学可以前往查看：[CCF-CSP真题附题解大全][CCF-CSP]

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202209-4</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>吉祥物投票</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>1.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>1.0GB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>题目描述</h3> <p>为了促进西西艾弗岛上的旅游业发展，当地决定设计一个吉祥物形象。活动吸引了众多设计领域的大师和爱好者参加，经过初步筛选，共选出了&nbsp;m&nbsp;个作品，编号为&nbsp;1∼m，进行最终的投票角逐。</p> <p>活动还吸引了西西艾弗岛上的&nbsp;n&nbsp;名投票者参与，编号为&nbsp;1∼n，每人都在最终的投票环节拥有投一票的权利，也可以放弃投票。我们定义每个人的投票意愿&nbsp;ai(1≤i≤n)&nbsp;为一个&nbsp;0∼m&nbsp;的整数，若&nbsp;ai=0&nbsp;表示这个人目前没有支持的作品，打算放弃投票，否则表示这个人支持第&nbsp;ai&nbsp;号作品并有意愿将票投给它。</p> <p>最初，由于所有人对参与竞选的作品都不了解，因此投票意愿&nbsp;ai&nbsp;均为&nbsp;0。接下来是紧张刺激的拉票环节，作品的设计者们要想方设法给自己的作品拉票，这一过程中可能出现如下若干种事件：</p> <p><code>1 l r x</code>：编号为&nbsp;x&nbsp;的作品开展了一场拉票活动，成功地吸引了编号为&nbsp;l∼r&nbsp;的投票者的兴趣，使得他们的投票意愿全部改为&nbsp;x。</p> <p><code>2 x w</code>：编号为&nbsp;x&nbsp;的作品需要经历一次大规模修改，所以需要暂时退出竞选。由于&nbsp;x&nbsp;与&nbsp;w&nbsp;两个作品的风格较为相近，因此原先投票意愿为&nbsp;x&nbsp;的投票者的投票意愿变为了&nbsp;w。特别地，若&nbsp;w=0，表示这些投票者暂时找不到新的支持的作品。需要注意的是，作品&nbsp;x&nbsp;退出竞选只是暂时的，因此后续的事件中作品&nbsp;x&nbsp;仍可能出现。</p> <p><code>3 x y</code>：主办方发现自己的统计出现了失误，将编号为&nbsp;x&nbsp;和&nbsp;y&nbsp;的作品弄颠倒了。发布勘误后，所有原先投票意愿为&nbsp;x&nbsp;的投票者的投票意愿变为了&nbsp;y，所有原先投票意愿为&nbsp;y&nbsp;的投票者的投票意愿变为了&nbsp;x。</p> <p><code>4 w</code>：主办方决定进行一次调查：希望知道所有投票者中，当前投票意愿为&nbsp;w&nbsp;的有多少人。若&nbsp;w≠0&nbsp;，相当于调查有多少投票者目前支持作品&nbsp;w&nbsp;，否则相当于调查有多少投票者目前没有支持的作品。</p> <p><code>5</code>：主办方决定进行一次调查：若以现在的投票意愿进行最终的投票，获胜的作品是哪一个。规定得票数至少为&nbsp;1&nbsp;且最多的作品获胜，得票数相同则编号较小的作品获胜。特别地，若所有作品均无得票，认为不存在获胜作品。</p> <p>从拉票开始到结束，共出现了&nbsp;q&nbsp;次如上的事件。由于参选的作品数和投票人数实在太多，单凭活动主办方的能力难以全面统计，现在请你编写一个程序来处理这些事件，并求出每次调查的结果。</p> <h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>第&nbsp;1&nbsp;行，3&nbsp;个正整数&nbsp;n,m,q。</p> <p>接下来&nbsp;q&nbsp;行，每行&nbsp;1∼4&nbsp;个非负整数，描述一个事件。</p> <h3>输出格式</h3> <p>输出到标准输出。</p> <p>对于每个&nbsp;4&nbsp;或&nbsp;5&nbsp;事件输出一行，一个非负整数表示此次调查的结果。其中事件&nbsp;5&nbsp;若不存在获胜作品则输出<code>0</code>。</p> <h3>样例输入</h3> 
    <blockquote> 
     <p>10 2 15<br> 5<br> 1 2 4 1<br> 1 4 7 2<br> 4 1<br> 5<br> 1 3 4 1<br> 5<br> 1 7 9 1<br> 3 1 2<br> 4 2<br> 2 1 2<br> 4 2<br> 2 2 0<br> 4 2<br> 5</p> 
    </blockquote> <h3>样例输出</h3> 
    <blockquote> 
     <p>0<br> 2<br> 2<br> 1<br> 6<br> 8<br> 0<br> 0</p> 
    </blockquote> <h3>评测用例规模与约定</h3> 
    <table> 
     <thead> 
      <tr> 
       <th>测试点编号</th> 
       <th>n≤</th> 
       <th>m≤</th> 
       <th>q≤</th> 
       <th>特殊性质</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>1∼4</td> 
       <td>10000</td> 
       <td>2000</td> 
       <td>2000</td> 
       <td>无</td> 
      </tr> 
      <tr> 
       <td>5∼7</td> 
       <td>109</td> 
       <td>2000</td> 
       <td>2000</td> 
       <td>无</td> 
      </tr> 
      <tr> 
       <td>8∼9</td> 
       <td>2×105</td> 
       <td>1</td> 
       <td>105</td> 
       <td>无</td> 
      </tr> 
      <tr> 
       <td>10∼11</td> 
       <td>2×105</td> 
       <td>105</td> 
       <td>105</td> 
       <td>r−l≤10，只有事件 1, 4, 5</td> 
      </tr> 
      <tr> 
       <td>12∼14</td> 
       <td>2×105</td> 
       <td>105</td> 
       <td>105</td> 
       <td>r−l≤10</td> 
      </tr> 
      <tr> 
       <td>15∼17</td> 
       <td>2×105</td> 
       <td>105</td> 
       <td>105</td> 
       <td>无</td> 
      </tr> 
      <tr> 
       <td>18∼20</td> 
       <td>109</td> 
       <td>105</td> 
       <td>105</td> 
       <td>无</td> 
      </tr> 
     </tbody> 
    </table><p>对于所有的数据，满足&nbsp;1≤n≤109，1≤m,q≤105，1≤l≤r≤n，1≤x,y≤m，0≤w≤m。保证事件&nbsp;2&nbsp;中&nbsp;x≠w，事件&nbsp;3&nbsp;中&nbsp;x≠y。</p> </td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[吉祥物投票][Link 1]

**解题思路：**

> 看了一眼感觉很容易理解，也就按照每个动作直白写了操作，最后果不其然内存超了，拿了20分

**20分题解(内存超限) ：**

n, m, q = map(int,input().split())
    people = [0 for i in range(n)]
    
    def pull(ticket):
        l = ticket[1]
        r = ticket[2]
        x = ticket[3]
        for i in range(l,r+1):
            people[i] = x
    
    def alter(ticket):
        x = ticket[1]
        w = ticket[2]
        for i in range(n):
            if people[i]==x:
                people[i] = w
    
    def exchange(ticket):
        x = ticket[1]
        y = ticket[2]
        for i in range(n):
            if people[i]==x:
                people[i] = y
            elif people[i]==y:
                people[i] = x
    
    def survey(ticket):
        w = ticket[1]
        if w != 0:
            print(people.count(w))
        else:
            print(people.count(0))
    
    def final():
        if sum(people)==0:
            print(0)
        else:
            temp = [0]*(m+1)
            for i in range(n):
                temp[people[i]] += 1
            print(temp[1:].index(max(temp[1:]))+1)
    
    for j in range(q):
        ticket = [i for i in map(int,input().split())]
        if ticket[0]==1:
            pull(ticket)
        elif ticket[0]==2:
            alter(ticket)
        elif ticket[0]==3:
            exchange(ticket)
        elif ticket[0]==4:
            survey(ticket)
        elif ticket[0]==5:
            final()

**运行结果：**

![08ea1f03cce74ac690c04cfada44ce97.png][]

--------------------

**满分题解：**

--------------------

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[Link 1]: http://118.190.20.162/view.page?gpid=T150
[08ea1f03cce74ac690c04cfada44ce97.png]: https://img-blog.csdnimg.cn/08ea1f03cce74ac690c04cfada44ce97.png