A
給出一個非遞減的陣列，問最少用幾種顏色染色，使得每一個顏色中的數嚴格遞增
明顯只要不是同一個數，就可以用同一種顏色染，因此記錄最多出現的數
#include <bits/stdc++.h>
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll read(){ll f=1;ll x=0;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f; }
inline ll quick_pow(ll a,ll b,ll mod) {ll ans=1,base=a;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 110;
void solve()
{
int a[maxn];
int n;
cin >> n;
int maxx = 0;
map<int,int> m;
rep(i,1,n)
{
scanf("%d", &a[i]);
m[a[i]]++;
maxx = max(maxx, m[a[i]]);
}
cout << maxx << '\n';
return;
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
B
q次詢問一個元素是否能由多個十進制中帶有d的數的和組成，
當一個數大于等于10d的時候必定有解，任何數都可以由(d10 + x) + nd組成
舉例，當d = 7時，明顯70-77是合法的，在到達77的時候，可以變化為70 + 7，此時明顯(70,70+7) + 7也就是77-84合法，以此類推，
當小于10d的時候，不斷減d，如果可以使得個位數為0，一定合法，因為可以在任意一個數中加上剩余得數使得合法，
舉例，d = 7,num = 58，當num減四次d的時候，則變成了7 + 7 + 7 + 7 + 30，明顯7+30 = 37是合法的，則可以變成7+7+7+37，
#include <bits/stdc++.h>
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll read(){ll f=1;ll x=0;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f; }
inline ll quick_pow(ll a,ll b,ll mod) {ll ans=1,base=a;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 1e4+10;
void solve()
{
int q,d;
cin >> q >> d;
while(q--)
{
int tmp;
cin >> tmp;
bool flag = false;
if(tmp >= 10 * d)
puts("YES");
else
{
while(tmp > 0)
{
if(tmp % 10 == d)
{
puts("YES");
flag = true;
break;
}
tmp -= d;
}
if(!flag)
puts("NO");
}
}
return;
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
C
由陣列a給出n對相反數，給出變化后的陣列d，變化為di=∑2nj=|ai?aj|，問能否由d陣列反推出唯一的a陣列
可以由第一個樣例分析
a = -1,1,-3,3
d = 8,8,12,12
看第一個數1，自身的相反數會對他產生一個貢獻，即2a1，第二個數及其相反數也會對其產生貢獻由于即|a1-a2|+|a1-(-a2)|
不妨假設a2大于a1，那么產生的結果就是a2-a1+a2+a1 = 2a2，因此不同的數aj對自身ai的貢獻等于2max(ai,aj)，
因此對陣列排序并去相反數后，最大的數的貢獻即是陣列長度(假設為n)乘這個數再乘2，次大的數的貢獻是(n-1)乘次大值乘2，再加上最大值乘2,以此類推，
#include <bits/stdc++.h>
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll read(){ll f=1;ll x=0;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f; }
inline ll quick_pow(ll a,ll b,ll mod) {ll ans=1,base=a;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 1e5+10;
ll a[maxn], d[maxn];
void solve()
{
int n;
cin >> n;
rep(i, 1, 2*n)
scanf("%lld", &d[i]);
sort(d + 1, d + 1 + 2 * n);
int tot=unique(d+1,d+1+2*n)-d-1;
if(tot != n) {
puts("NO");
return;
}
ll suf = 0;
bool flag = true;
/*for (int i = 1;i <= n;i++)
{
cout << d[i] << " ";
}
cout << '\n';*/
per(i,n,1)
{
if((d[i] - suf) % (2*i) ||d[i] <= suf )
{
flag = false;
break;
}
a[i] = (d[i] - suf) / (2 * i);
suf += 2 * a[i];
}
if(flag)puts("YES");
else
puts("NO");
/*for (int i = 1;i <= n;i++)
cout << a[i] << " ";
cout << '\n';*/
return;
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
D
選兩個數，產生一個2*x-y的數，問是否能產生一個k
相當于產生x + x - y
考慮兩個數的情況，由于兩個數的差值一定是兩個數最大公因數的倍數，因此兩個數輾轉相減能得到他們的最大公因數，多個數則是多個數的最大公因數，則最小單位就是這n個數差的最大公因數，
由于本題可以存在負數，因此只要任意找其中一個數驗證即可
#include <bits/stdc++.h>
using namespace std;
#define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define ll long long
inline ll quick_pow(ll a,ll b,ll mod) {ll ans=1,base=a;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;}
inline ll inv(ll x,ll p){return quick_pow(x,p-2,p);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const double pi=acos(-1.0);
const ll inf = LONG_LONG_MAX;
const ll mod = 998244353;
const ll maxn = 1e5 + 10;
void solve()
{
ll n, k;
cin >> n >> k;
ll a[n + 2];
rep(i, 1, n)
{
cin >> a[i];
}
ll factor = a[2]-a[1];
rep(i,3,n)
{
factor = __gcd(factor, a[i] - a[i - 1]);
}
if((k-a[1])%factor == 0)
puts("YES");
else
puts("NO");
return;
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
后續待補
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/254471.html
標籤：其他
上一篇：電子設備分享