我TM肝爆
A - Sequence with Digits
- 题意:
a(n+1)=an+an(每一位的最大)*an(每一位的最小)，已知a1, k，求ak。
- 思路:
当an的位数拆出来0的时候，后面an的值会陷入循环，即不用再进行计算，那么判断当前位数是否拆出来0即可
int main()
{
IOS;
int T;
cin >> T;
while (T--)
{
ll n, k;
cin >> n >> k;
k--;
ll bef,num = 0;
while (k--)
{
ll now = n;
ll minn = 999, maxn = -1;
while (now)
{
minn = min(now % 10, minn);
maxn = max(now % 10, maxn);
now /= 10;
}
if(minn*maxn==0)
break;
n+=minn*maxn;
}
cout<<n<<endl;
}
return 0;
}
B - Young Explorers
- 题意:
给定一些值，要将这些值分组，要求每个组内的最大值必须小于该组大小，求最多分组数量。
- 思路:
先将这些值排序，每次贪心的取花费最少数量元素，使这些元素就可以构成题目要求的组。
solve 1:
每到一个数先++cnt，如果这时cnt==当前的a[i]说明能凑成一组了，直接ans++，同时cnt=0置零。
贪心策略就是用尽可能少的数凑出来一组,因此要从小到大遍历。
int n,a[200005];
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
int i;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
int ans=0;
int cnt=0;
a[n+1]=0x3f3f3f3f;
for(i=1;i<=n+1;i++)
{
cnt++;
if(a[i]==cnt)
{
ans++;
cnt=0;
}
}
cout<<ans<<endl;
}
}
solve 2:
直接计算：利用map，当前元素最多可以分的组数即为map[i]/i，如果有多余的元素就传给下一次计算。
int a[200005];
map<int, int> mp;
int main()
{
IOS;
int T;
cin >> T;
while (T--)
{
mp.clear();
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
mp[a[i]]++;
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
ans += (mp[i] / i);
mp[i + 1] += mp[i] % i;
}
cout << ans << endl;
}
return 0;
}
C - Count Triangles
- 题意:
给定A，B，C，D，要求算出三边z,y,z满足 A <= x <= B <= y <= C <= z <= D 的三角形的个数
- 思路:
真是好题啊。。奈何自己数学差，，哎
枚举x+y的值，此时x的数量=y的数量，那么只需要通过x+y来计算x，z的范围即可，详细见代码。
int main()
{
IOS;
ll A,B,C,D;
cin>>A>>B>>C>>D;
ll ans=0;
for(ll i=max(A+B,C+1);i<=B+C;i++)
// 根据x+y>z可知x+y的最大范围为[max(A+B,C+1),B+C]
// 关于C+1: 例如2 3 6 10,此时x=2,y=3,z最小要取6,不合法
{
ll l=max(A,i-C), r=min(B,i-B); // x的最大范围[l,r]
if(l<=r)
ans+=(r-l+1)*(min(i-1,D)-C+1);
// 因为x+y>z ,故z可取的最大值为min(i-1,D)。
}
cout<<ans;
return 0;
}
D - Game With Array
- 题意:
给定 n，s，要求构造长度为n的序列以及k，要求序列总和sum=k或者sum=s-k。
- 思路:
因为序列的值必须>=1，也就是说需要满足k>=s-(n-1), 也就是k的极限情况。那么只需要构造1 1 1 … s-(n-1)即可。
int main()
{
IOS;
int n, s;
cin >> n >> s;
int t = s - (n - 1);
if (t <= n)
cout << "NO" << endl;
else
{
cout << "YES" << endl;
for (int i = 1; i <= n - 1; i++)
cout << 1 << " ";
cout << t << endl;
cout << n << endl;
}
return 0;
}