智算の道第一場

20824 ワード

第一題
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int a[110],b[maxn];
int n,t,m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i%a[j]==0)
				b[i]=1;
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(b[i]==0)
			cnt++;
	cout<<cnt;
	return 0;
}

第二題
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int a[maxn];
int n;
int main()
{
	string s;
	cin>>n;
	cin>>s;
	char t;
	int cnt=0;
	int i,j;
	t=s[0];
	for(i=1;i<s.length();i++)
	{
		if(t!=s[i])
		{
			t=s[i];
			cnt++;
		}
	}
	if(t=='1')
		cnt++;
	cout<<cnt;
	return 0;
}

第三題
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int a[110],b[110],tt[110];
int ss[maxn][30],d[maxn][30];
int n,m;
set<string> st;
char s[maxn],t[maxn];
int main()
{
	string s,t;
	//scanf("%s",&s);
	//scanf("%s",&t);
	cin>>s>>t;
	for(int i=0;i<s.length();i++)
	{
		a[s[i]-'a'+1]++;
	}
	for(int i=0;i<t.length();i++)
	{
		d[i+1][t[i]-'a'+1]++;
		//cout<
	}
	for(int j=1;j<=26;j++)
	{
		for(int i=1;i<=t.length();i++)
		{
			ss[i][j]=ss[i-1][j]+d[i][j];
		}
	}
	int k=s.length();
	for(int i=1;i<=t.length()-k+1;i++)
	{
		int flag=1;
		for(int j=1;j<=26;j++)
		{
			tt[j]=ss[i+k-1][j]-ss[i-1][j];
			//cout<
			if(tt[j]!=a[j])
				flag=0;
		}
		if(flag)
		{
			string temp;
			temp=t.substr(i-1,k);
			st.insert(temp);
		}
	}
	int cnt=st.size();
	cout<<cnt;
	return 0;
}