智算之道2020第一场初赛题解报告

た入场券 2023-02-26 02:26 13阅读 0赞

# T1 #

#include <iostream>
    using namespace std;
    
    const int N = 100005;
    bool a[N];
    
    int main()
    { 
        int n, m;
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
        { 
            a[i] = 1;
        }
    
        int t;
        for(int i = 1; i <= m; i++)
        { 
            cin >> t;
            for(int i = 1; i <= n; i++)
            { 
                if(i % t == 0)
                { 
                    a[i] = 0;
                }
            }
        }
    
        int cnt = 0;
        for(int i = 1; i <= n; i++)
        { 
            cnt += a[i];
        }
    
        cout << cnt;
    
        return 0;
    }

# T2 #

## 解法一：枚举，60分 ##

#include <bits/stdc++.h>
    using namespace std;
    
    string change(string s)
    { 
        int len = s.size();
        int pos;
        for(int i = len - 1; i >= 0; i--)
        { 
            if(s[i] == '1')
            { 
                pos = i;
                break;
            }
        }
    
        for(int i = 0; i <= pos; i++)
        { 
            if('1' == s[i])
            { 
                s[i] = '0';
            }
            else
            { 
                s[i] = '1';
            }
        }
    
        return s;
    }
    
    int main()
    { 
        //freopen("T2.in", "r", stdin);
    
        int n;
        string s;
        cin >> n >> s;
        string target;
        for(int i = 0; i < n; i++)
        { 
            target.push_back('0');
        }
    
        int cnt = 0;
        while(s != target)
        { 
            s = change(s);
            cnt++;
        }
    
        cout << cnt;
        return 0;
    }

## 解法二 ##

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    typedef long long LL;
    const int maxn = 2e5+10;
    int a[maxn];
    
    int main()
    { 
        int n;
    	string s;
    	cin >> n >> s;
    
    	int cnt = 0;
    	char lastC = s[0];
    	for(int i = 1; i < s.length(); i++)
    	{ 
    		if(lastC != s[i])
    		{ 
    			lastC = s[i];
    			cnt++;
    		}
    	}
    
    	if(lastC == '1')
        { 
            cnt++;
        }
    
    	cout << cnt;
    
    	return 0;
    }

# T3 #

## 解法一：枚举，30分 ##

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        //freopen("T3.in", "r", stdin);
    
        string s, t;
        cin >> s >> t;
        sort(s.begin(), s.end());
    
        int cnt = 0;
        do
        {
            if(string::npos != t.find(s))
            {
                cnt++;
            }
        }while(next_permutation(s.begin(), s.end()));
    
        cout << cnt;
    
        return 0;
    }

# 解法二：尺取法+map去重 #

#include<bits/stdc++.h>
    using namespace std;
    
    int main()
    { 
        //freopen("T3.in", "r", stdin);
    
        int cnt = 0;
        string s, t, subT;
        cin >> s >> t;
    
        map<string, bool> vis; //判断字符串是否被遍历过
        int cnt1[123]={ 0}, cnt2[123]={ 0};//a~z的ASCII码是97~122
    
        int sLen = s.length(), tLen = t.length();
        for(int i=0; i<sLen; i++)
        { 
            cnt1[s[i]]++;
        }
    
        for(int startPos=0; startPos <= tLen - sLen; startPos++)
        { 
            if(startPos==0)
            { 
                for(int j=0; j < sLen; j++)
                { 
                    cnt2[t[j]]++;
                }
            }
            else
            { 
                //整体往右挪动一个位置，长度仍为sLen
                cnt2[t[startPos - 1]]--;
                cnt2[t[startPos + sLen - 1]]++;
            }
    
            bool same = true;//s各字符数量是否与t的子串各字符数量一样
            for(int j='a'; j<='z'; j++)
            { 
                if(cnt1[j] != cnt2[j])
                { 
                    same=false;
                }
            }
    
            //subT是t中长度为sLen的子串
            subT = t.substr(startPos, sLen);
            if(same && !vis[subT])
            { 
                vis[subT]=true;
                cnt++;
            }
        }
    
        cout << cnt;
    
        return 0;
    }

了解信息学竞赛请加微信307591841邀请入群