首页 > 其他分享 >week16

week16

时间:2023-10-16 18:12:19浏览次数:34  
标签:week16 int ll cin long ans MOD

Week 16

目录

div2 代码源每日一题

501 RSA

  • 质数正常判断即可

  • A*B大于1的整数的平方的整数倍可以转换成 A和B有公因子 或 A或B中有因子是某个大于1的整数的平方的整数倍

    #include<iostream>
    #include<cmath>
    #include<map>
    using namespace std;
    bool isprime(long long x)	//判断是不是质数
    {
    	if(x==1)return 0;
    	for(int i=2;i<=sqrt(x);i++)
    	{
    		if(x%i==0)return 0;
    	}
    	return 1;
    }
    bool flag=0;
    map<long long,int>mymap;
    bool check(long long a)
    {
    	for(int i=2;i<=sqrt(a);i++)
    	{
    		if(a%i==0)
    		{
    			mymap[i]++;
    			mymap[a/i]++;
    			if(mymap[i]>=2||mymap[a/i]>=2)
    			{
    				flag=1;	
    				return 1;
    			}
    		}
    	}
    }
    int main()
    {
    	std::ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	long long a,b;
    	
    	cin>>a>>b;
    	if(a==b)
    	{
    		cout<<"no credit";
    		return 0;
    	}
    	if(isprime(a)&&isprime(b))
    	{
    		cout<<"full credit";
    		return 0;
    	}
    	check(a);
    	check(b);
    	if(flag==1)
    	{
    		cout<<"no credit";
    	}
    	else
    	{
    		cout<<"partial credit";
    	}
    	return 0;
    }
    
    

503 A-B 数对

  • A-B=C转换成A-C=B,用map存B
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,c,ans;
ll a[N];
map<int,int>mp;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>c;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		mp[a[i]]++;//存的是b 
		a[i]-=c; //A-C 
	}
	
	for(int i=0;i<n;i++)
	{
		ans+=mp[a[i]];
	}
	cout<<ans<<endl;
	return 0;
 } 

504 数位计算

  • 19,1099,100~999,每个位数一样的为一档,同一档中,f(n)-f(n-1)=1

    等差数列求和

  • 思路:先求出n的最大位数,然后再处理,记得每一步都要取模

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int MOD=998244353;
    ll ans,n1;
    string n;
    int main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	
    	cin>>n;
    	int len=n.length();
    	for(int i=0;i<len;i++)
    	n1=n1*10+(ll)(n[i]-'0');
    	if(n1<10)
    	{
    		ans+=(1+n1)*n1/2;
    		cout<<ans<<'\n';
    		return 0;
    	}
    	ll k=pow(10,len-1);
    	ans+=45;
    	ll x=(n1-k+2)%MOD;
    	ll y=(n1-k+1)%MOD;
    	ans+=(x*y/2)%MOD;
    	while(k/10>=10)
    	{
    		x=(k-k/10+1)%MOD;
    		y=(k-k/10)%MOD;
    		ans+=(x*y/2)%MOD;
    		k/=10;
    	}
    	cout<<ans%MOD<<'\n';
    	return 0;
    }
    

505 新国王游戏

  • 两两之间,判断a在b前面得到的结果大 还是 b在a前面得到的结果大

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const ll MOD=1000000007;
    const ll N=1e6+10;
    ll n,ans=0,sum=1;
    struct Peo{
    	ll a,b;
    }peo[N];
    
    bool cmp(Peo a,Peo b)
    {
    	return b.b +a.b *b.a  < a.b +b.b *a.a  ;
    }
    
    int main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
    		cin>>peo[i].a >>peo[i].b ;
    		peo[i].a%=MOD;
    		peo[i].b%=MOD;
    	}
    	
    	sort(peo,peo+n,cmp);
    	ans+=peo[0].b ;	
    
    	for(int i=0;i<n;i++)
    	{
    		if(i>0)
    		ans=(ans+(sum*peo[i].b )%MOD)%MOD;
    		ans%=MOD;
    		sum=(sum*peo[i].a )%MOD;
    	}
    	
    	cout<<ans%MOD<<'\n';
    	return 0;
    }
    

506 完美数

  • x个a和(m-x)个b排列组合,用sum记录x个a和(m-x)个b的和,然后再判断sum是不是由a和b组成即可
  • 注意有重复元素的排列组合公式
#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<ll, ll>PII;
const int MOD = 1e9 + 7, N = 1e6 + 10;
ll fact[N], infact[N];

ll qmi(int a, int b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a % MOD;
        a = a * (ll)a % MOD;
        b >>= 1;
    }
    return res;
}

void init()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++)
        fact[i] = fact[i - 1] * i % MOD;

    infact[N - 1] = qmi(fact[N - 1], MOD - 2);
    for (int i = N - 2; i; i--)
        infact[i] = infact[i + 1] * (i + 1) % MOD;
}

int C(int a, int b)
{
    return (fact[a] * infact[b] % MOD * infact[a - b] % MOD) % MOD;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int a, b, m;
    cin >> a >> b >> m;
    init();
    char c = a + '0', d = b + '0';
    int x;
    ll res = 0;
    for (int i = 0; i <= m; i++)
    {
        x = m - i;
        ll num = x * a + i * b;
        bool flag = true;
        while (num)
        {
            if (num % 10 != a && num % 10 != b)
            {
                flag = false;
                break;
            }
            num /= 10;
        }
        if (!flag)continue;
        res = (res + C(m,i)) % MOD;
    }
    cout << (res%MOD) << endl;
    return 0;
}

507 Lusir的游戏

  • 二分答案

  • 注意:如果e>h_max,e就会不断增加,后面可能会超long long,所以check里加一个判断return true

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N=1e5+10;
    ll n,l=1,r,ans,max_value;
    ll h[N];
    bool check(ll e)
    {
    	for(int i=1;i<=n;i++)
    	{
    		if(h[i]>e)
    		e-=h[i]-e;
    		else
    		e+=e-h[i];
    		if(e<0)
    		return false;
    		if(e>=max_value) return true;
    	}
    	return true;
    }
    int main()
    {
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cout.tie(0);
    	
    	cin>>n;
    	
    	for(int i=1;i<=n;i++)
    	{
    		cin>>h[i];
    		r+=h[i];
    		max_value=max(h[i],max_value);
    	}
    	
    	while(l<=r)
    	{
    		ll mid=l+(r-l)/2;
    		if(check(mid)) 
    		{
    			ans=mid;
    			r=mid-1;
    		}
    		else 
    		l=mid+1;
    	}
    	cout<<ans<<'\n';
    	return 0;
    }
    

601 BFS练习1(广度优先)

  • 每一个数字对应四种可能,一层一层搜树,搜到需要的数字就把答案存下来。当存了q个时,结束。

    #include<bits/stdc++.h>
    using namespace std;
    const int N=300050;
    int vis[N],ans[N];
    int step,a,q;
    int main()
    {
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cout.tie(0);
    	
    	queue<int> que;
    	
    	cin>>a>>q;
    	que.push(a);
    	vector<int> v(q);
    	for(int i=0;i<q;i++)
    	{
    		cin>>v[i];
    		ans[v[i]]=-1;
    	}
    	
    	while(!que.empty()&&q)
    	{
    		int len=que.size(); //important!!!这样保证每一层step+1 ,而不是每push一次step+1 
    		for(int i=0;i<len;i++)
    		{ 
    		int now=que.front();
    		que.pop();
    		if(ans[now]==-1)
    		{
    			ans[now]=step;
    			q--;
    		}
    		if(now*3<N&&vis[now*3]==0)
    		{
    			que.push(now*3);
    			vis[now*3]=1;
    		}
    		if(now*2<N&&vis[now*2]==0)
    		{
    			que.push(now*2);
    			vis[now*2]=1;
    		}
    		if(now+1<N&&vis[now+1]==0)
    		{
    			que.push(now+1);
    			vis[now+1]=1; 
    		}
    		if(now-1&&vis[now-1]==0)
    		{
    			que.push(now-1);
    			vis[now-1]=1;
    		}
    	}
    		step++;
    		
    	}
    	
    	for(auto i:v)
    	{
    		cout<<ans[i]<<" ";
    	}
    	
    	return 0;
    }
    

602 01序列 2

  • 从0到n枚举1的数量,0的数量为(i-1)*k

    删掉每两个1之间的k个0,该01串还剩n-(i-1)*k个,

    默认每两个1之间都有k个0,这些是固定的。那么01串的长度就是n-(i-1)*k个。

    C(i)(n-(i-1)*k)

  • 注意1:除法不能取模,引入逆元

    • 概念:在mod p的意义下, 有(a*b) mod p = 1,则称b为a的乘法逆元,为方便我们记作inv(b);

    • 性质:a/b mod p == a*inv(b) mod p

    • 求逆元:费马小定理:pow(b, p-1) mod p =1

      所以pow(b, p-2)即为在mod p意义下,b的乘法逆元

      ll inv(ll a)
      {
      	return pow(a,MOD-2)%MOD;
      }
      
  • 注意2:快速幂

    ll quick_pow(ll a, ll b)
    {
    	ll ans=1;
    	while(b)
    	{
    		if(b&1)//判断奇偶,偶为0,奇为1
    		ans=ans*a%MOD;
    		a=a*a%MOD;
    		b>>=1;
    	}
    	return ans;
    }
    
  • AC代码

    #include <iostream>
    using namespace std;
    const int max_n = 1e6;
    const int max_k = max_n;
    const long long mod_num = 1e9 + 7;
    
    int n, k;
    long long factorial[max_n + 1];
    
    long long pow(long long x, long long y, long long p) {
    	long long ret = 1;
    	while (y) {
    		if (y & 1) ret = (ret * x) % p;
    		x = (x * x) % p;
    		y >>= 1;
    	}
    	return ret;
    }
    
    long long inv(long long x, long long p) {
    	return pow(x, p - 2, p);
    }
    
    long long cmd(long long m, long long n) {
    	long long num1 = factorial[n];
    	long long num2 = factorial[m];
    	long long inv2 = inv(num2, mod_num);
    	long long num3 = factorial[n - m];
    	long long inv3 = inv(num3, mod_num);
    	return ((num1 * inv2) % mod_num) * inv3 % mod_num;
    }
    
    int main() {
    	factorial[0] = 1;
    	for (int i = 1; i <= max_n; i++) factorial[i] = factorial[i - 1] * i % mod_num;
    
    	cin >> n >> k;
    	int max_ones = (n + k) / (k + 1);
    	long long ans = 1;
    	for (int i = 1; i <= max_ones; i++) {
    		int left = n - (i - 1) * k + 1;
    		ans = (ans + cmd((i + 1) - 1, left - 1)) % mod_num;
    	}
    	cout << ans << endl;
    	return 0;
    }
    

603 整除光棍

  • 想麻烦了一点写了个高精度除法

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e6+10;
    string s;
    int js;
    int ss[N],res[N];
    bool check(int x,int len)
    {
    	long long yu=0;
    	for(int i=0;i<len;i++)
    	ss[i]=(int)(s[len-i-1]-'0');
    	
    	for(int i=0;i<len;i++)
    	{
    		yu=yu*10+ss[i];
    		if(yu>=x)
    		{
    			res[js]=yu/x;
    			yu=yu-x*res[js];
    		}
    		else
    		res[js]=0;
    		js++;
    	}
    	
    	if(yu==0)
    	return true;
    	else
    	return false;
    }
    
    
    int main()
    {
    	int len=0,x;
    	cin>>x;
    	while(1)
    	{
    		ss[N]={0};
    		res[N]={0};
    		js=0;
    		len++;
    		s+='1';
    		if(check(x,len))
    		{
    			int i=0;
    			while(res[i]==0)
    			{
    				i++;
    			}
    			
    			for(;i<js;i++)
    			cout<<res[i];
    			cout<<" "<<len;
    			break;
    		}
    	}
    	return 0;
     } 
    
  • 简化:

    #include<stdio.h>
    int main(){
    	int s=1,n,num=0,k=0;
    	scanf("%d",&n);
    	while(1){
    		if(s/n!=0)k=1;
    		num++;
    		if(k)printf("%d",s/n);
    		s=s%n;
    		if(s==0)break;
    		s=s*10+1;
    	}
    	printf(" %d",num);
    }
    

604 碰撞

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n;
struct Peo{
	int x,y;
	char dir;
}peo[N];
bool cmp(Peo a,Peo b)
{
	if(a.y ==b.y )
	return a.x <b.x ; //按x升序 
	return a.y >b.y ; //按y降序 
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
		cin>>peo[i].x>>peo[i].y ;
	}
	for(int i=0;i<n;i++)
	{
		cin>>peo[i].dir ;
	}
	
	sort(peo,peo+n,cmp);
	for(int i=1;i<n;i++)
	{
		if(peo[i].y==peo[i-1].y&&peo[i].dir =='L'&&peo[i-1].dir=='R' )
		{
			cout<<"Yes";
			return 0; 
		}
		
	 } 
	
	cout<<"No";
	return 0;
}

刷题

P4913 二叉树深度

  • 基础树的存储和遍历

  • 存储用node数组

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e6+10;
    int ans,n;
    struct node{
    	int left,right; //左结点编号和右结点编号 
    }tree[N];
    
    void dfs(int id, int deep)
    {
    	if(id==0) return ;
    	ans=max(ans,deep);
    	dfs(tree[id].left ,deep+1);
    	dfs(tree[id].right ,deep+1);
    }
    
    int main()
    {
    	ios::sync_with_stdio;
    	cin.tie(0);
    	cout.tie(0);
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	cin>>tree[i].left >>tree[i].right ;
    	dfs(1,1);
    	cout<<ans<<endl;
    	return 0;
     } 
    

标签:week16,int,ll,cin,long,ans,MOD
From: https://www.cnblogs.com/xiaoyangii/p/17768025.html

相关文章

  • 2024备考408Week16
    一、本周总结:使用时间:(离每周目标40h还差10h,差距还很大!)总计30h,数学12h50min,专业课12h9min,英语3h40min,政治1h21min。二、存在问题:1.数学、专业课(DS+OS+CO+CN)做题训练不够,思考不够深入,计算不够熟练和准确,后期一定要开始加强了;2.碎片化时间和整块时间没有合理安排,碎片化时间应该安排......
  • 考研周记-week16
    准时的周记6.5~6.11记录一下本周的考研进度情况英语本周继续单词的复习,因为最近一直在赶数学的进度,所以将单词放在了晚上回宿舍之后在背,等到线代过完一轮,就恢复正常的英语复习数学数学方面,本周结束了概率论的复习,线性代数也进行了一半,准备下周结束数学一基础阶段的第一轮复......