首页 > 其他分享 >CF 1807

CF 1807

时间:2023-04-04 15:00:29浏览次数:54  
标签:1807 cnt int memset CF cas sizeof

https://codeforces.com/contest/1807/problem/G1

 

easy -version  同《货币系统》

背包

f[ j ] 每个数字合成的次数

#include <iostream>
#include <cstring>
using namespace std ;
 const int M=5006,N=5006;
 int n,a[N],cnt[M],f[M];

 bool solve(){
 	int i,j;
 	
 	memset(cnt,0,sizeof cnt) ;
 	cin>>n;
 	  for(i=1;i<=n;i++) cin>>a[i],cnt[a[i]]++;
	if(n==1){
		if(a[1]==1) return 1;return 0;
	}
 	memset(f,0,sizeof f);
 	f[0]=1;
 	for(i=1;i<=n;i++)
 	 for(j=5000;j>=a[i];j--)
 	 	 f[j]+=f[j-a[i]];
	

	for(i=1;i<=n;i++) 
		if((f[a[i]]==cnt[a[i]])&&a[i]!=1) return 0;
	return 1;
 }
 signed main(){
 	int cas;
 	cin>>cas;
 	while(cas--){
 	  if(solve()) cout<<"YES";else cout<<"NO";
 	  cout<<endl;
 	}
 }

 
 

 

标签:1807,cnt,int,memset,CF,cas,sizeof
From: https://www.cnblogs.com/towboa/p/17286420.html

相关文章

  • Hot Start Up (easy version) CF1799
    你有两个CPU,n个程序(m个类型)要运行。在不同条件下程序运行的时间不同,但连续运行的时间满足小于等于在不连续状态下运行的时间。  #include<iostream>#include<cstring>#include<queue>usingnamespacestd;constintN=5002;#defineintlonglong#definei......
  • cf-div.2-862d
    题目链接:https://codeforces.com/contest/1805/problem/D赛时没过的题。思路:首先发现一个性质:对于k来说,如果树上的一个点到树的直径的两个端点的距离都小于k的话,那么这个点一定是一个孤立点。证明:采用反证法:假设\(x,y\)为树的直径的两个端点,\(a,b\)为另外两个点,且有\(d[a][x]<k......
  • [I]CF With AT
    EducationalCodeforcesRound127(RatedforDiv.2)A显然,长度\(2\)和\(3\)能拼出任意长度字符串,所以无解情况考虑有没有单独的长度为\(1\)的即可。/*byL1rs1ngzN1sLyr*/#include<bits/stdc++.h>constintAI=1e3+9;constintKI=1e6+2;constintCI=1e7+3;i......
  • CF594A Warrior and Archer 题解
    由于本人在思索了很久后才把本题思路打通,所以为了帮助像我一样没有非常理解解法的人,我打算再将解法非常详细地叙述一遍,如果您无法理解解法,请跟着我再一步步将题目捋顺。Step.1解题意题目要求其实很好理解,共给出\(n\)个点的位置,A,B两个人轮流取点,A要求最后剩下的两个点尽量近,B......
  • CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)(CF1810)A~D题题解
    今天采用的是新格式。CF1810ABeautifulSequence点击查看原题点击查看思路如果一个数字的值\(v\),不大于当前的位置\(p\),那我们可以通过删除\(p-v\)个数字,使它们两个对应上。比如\([1,7,2,5,3]\)中的\(3\),其数值为\(3\),位置为\(5\),数值\(3\)小于等于\(......
  • cf-div.2-860d
    题目链接:https://codeforces.com/contest/1798/problem/D贪心,比赛时一直搞C没搞出来,回头看D反而更简单。贪心策略:能填正数就填,填不了填负数。大致证明:构造的区间一定呈一个这样的特定区间,正...负正负负...负正....负负,证明一段区间为正且小于给定值易证,下面证最后一段区间的绝......
  • CF1187E
     换根dp#include<iostream>#include<algorithm>#include<cstring>#include<queue>#defineIOSstd::ios::sync_with_stdio(0)usingnamespacestd;#defineintlonglongconstintN=2e5+20;intn,sz[N],f[N],G[N];vector<int>g[......
  • CF453B
    Solution观察范围\(a_i\le30\)比较特殊,于是我们可以试着考虑\(b\)的范围。直觉告诉我们\(b\)不会很大,当\(b_i\le59\)时,有\(|a_i-b_i|\le29\)。当\(b_i>59\)时,\(|a_i-b_i|>29\),但是如果这时我们将\(b_i\)换成\(1\),也是满足互质的,且\(|a_i-b_i|\)可以变得更......
  • PCF8591(A/D,D/A 转换)
    PCF8591芯片介绍PCF8691是具有IIC总线接口的8位A/D及D/A转换器。有4路A/D转换输入,1路D/A模拟输出,具体如下图。标志引脚描述AIN01模拟输入通道1(A/D转换器)AIN12模拟输入通道2(A/D转换器)AIN23模拟输入通道3(A/D转换器)AIN34模拟输......
  • cf-div2-860c
    题目链接:https://codeforces.com/contest/1798/problem/C大致题意:给你一个长度为\(n(n<=2e5)\)的序列的\(a_i,b_i\),让你把这个序列分成数目最少的段,每一段都有一个值\(c\),\(c=a_i的一个约数乘以b_i\)。比赛没写出的题。思路:\(首先一段里面的所有a_i*b_i能够整除c,易得c是所有b的......