Codeforces Round#574(Div.2)A,B,C,D 1,D 2題解
A. Drinks Choosing
最初は題意に引っかかって、最初はいくら買うかと思っていたが、後に買ったものがどれだけの人に飲めるかを発見した.
B. Sport Mafia
入れた個数が累加されているので、砂糖があるときは先に入れて食べるのと変わらないので、法則を見つければいいのです
C. Basketball Exercise
左から右の各列の3つの場合、1行目の人、2行目の人、1行目の2行目の人は取りません.
D1. Submarine in the Rybinsk Sea (easy edition)
各数字の各桁の寄与を考慮し,加算して和を求める
D2. Submarine in the Rybinsk Sea (hard edition)
問題の意味は前の問題と同じですが、前の問題で与えられた数字はすべて等長で、貢献値は計算しやすいので、この問題は等長でないと少し問題があります.
最初は題意に引っかかって、最初はいくら買うかと思っていたが、後に買ったものがどれだけの人に飲めるかを発見した.
#include
#define int long long
using namespace std;
const int maxn = 1010;
int vis[maxn];
signed main()
{
ios::sync_with_stdio(false);
int n,k,tmp;
cin >> n >> k;
for(int i = 1;i <= n; ++i)
{
cin >> tmp;
vis[tmp]++;
}
tmp = 0;
for(int i = 1;i <= k; ++i)
tmp += vis[i] / 2;
cout << (n+1)/2-tmp+tmp*2 << endl;
return 0;
}
B. Sport Mafia
入れた個数が累加されているので、砂糖があるときは先に入れて食べるのと変わらないので、法則を見つければいいのです
#include
#define int long long
using namespace std;
signed main()
{
ios::sync_with_stdio(false);
int n,k,sum = 0,i;
cin >> n >> k;
for(i = 1;sum - (n - i + 1) < k; ++i)
sum += i;
cout << n - i + 1 << endl;
return 0;
}
C. Basketball Exercise
左から右の各列の3つの場合、1行目の人、2行目の人、1行目の2行目の人は取りません.
#include
#define int long long
using namespace std;
const int maxn = 1e5+10;
int a[maxn],b[maxn],dp[maxn][5];
signed main()
{
ios::sync_with_stdio(false);
int n,k,sum = 0,i;
cin >> n;
for(int i = 1;i <= n; i++)
cin >> a[i];
for(int i = 1;i <= n; i++)
cin >> b[i];
for(int i = 1;i <= n; i++)
{
dp[i][0] = max(max(dp[i-1][0],dp[i-1][1]),dp[i-1][2]);
dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + a[i];
dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + b[i];
}
cout << max(dp[n][0],max(dp[n][1],dp[n][2])) << endl;
return 0;
}
D1. Submarine in the Rybinsk Sea (easy edition)
各数字の各桁の寄与を考慮し,加算して和を求める
#include
#define int long long
using namespace std;
const int mod = 998244353;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,mp,ans = 0;
cin >> n;
for(int i = 0;i < n; i++)
{
cin >> mp;
int xx = 0,pos = 1;
while(mp)
{
xx = (xx + (((mp % 10) * pos) % mod) * 11) % mod;
pos *= 1ll*100;
mp /= 10;
}
xx = (xx * n) % mod;
ans = (ans + xx) % mod;
}
cout << ans << endl;
return 0;
}
D2. Submarine in the Rybinsk Sea (hard edition)
問題の意味は前の問題と同じですが、前の問題で与えられた数字はすべて等長で、貢献値は計算しやすいので、この問題は等長でないと少し問題があります.
#include
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 1e5+10;
int cnt[15],x[maxn][15],sum;
void Cal(int tmp,int base,int y)
{
while(tmp)
{
sum += base * (tmp % 10) % mod;
sum %= mod;
if(y > 0)
base *= 100*1ll;
else
base *= 10*1ll;
base %= mod;
tmp /= 10;
y--;
}
}
signed main()
{
//freopen("in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int n,xx;
cin >> n;
for(int i = 1;i <= n; i++)
{
cin >> xx;
int tmp = 0,y = xx;
while(y)
{
tmp++;
y /= 10;
}
x[cnt[tmp]++][tmp] = xx;
}
int ans = 0;
for(int i = 1;i <= 10; i++)
{
for(int j = 1;j <= 10; j++)
{
for(int k = 0;k < cnt[i]; k++)
{
if(cnt[j] == 0)
continue;
sum = 0;
Cal(x[k][i],1,j);
Cal(x[k][i],10,j-1);
sum = (sum * cnt[j]) % mod;
ans = (ans + sum) % mod;
}
}
}
cout << ans << endl;
return 0;
}