目录
N Particle Arts
题目
n个数字，对于a和b碰撞后，变为a&b与a|b求，方差最大值
分析
通过观察发现，通过碰撞，二进制的0与1个数不会发生变化，及数字总和不会发生变化。结合整体数字相差越大方差越小。
代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=20,M=5e5+5;
int n;
ll sum=0;
int a[N];
ll gcd(ll a,ll b) {
return b==0?a:gcd(b,a%b);
}
int main(){
int n,x;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>x;
sum+=x;
for(int j=0;j<16;j++) {
a[j]+=((x>>j)&1);
}
}
ll fen=0,mu=1ll*n*n;
for(int i=1;i<=n;i++) {
ll t=0;
for(int j=15;j>=0;j--) {
if(a[j]) {
t |= (1<<j);
a[j]--;
}
}
fen+=t*t;
}
ll l=sum*sum,d;
fen*=n;
fen = fen-l;
if(fen==0) {
cout<<"0/1";
} else {
d=gcd(fen,mu);
cout<<fen/d<<"/"<<mu/d;
}
return 0;
}
K NIO's Sword
题目
初始A=0,每次更新一次x,使得A=A*10+x。给定n,最少几次实现A≡ i(mod n)
分析
对于第i轮，一定有A≡ i-1 (mod n) ，此时A等价转化与i-1。设要进行t次替换
则 对于t只要判断对应的x是否在范围内即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=20,M=5e5+5;
int n,ans=0;
int a[N];
int main(){
int n;
cin>>n;
if(n==1) {
printf("0");
return 0;
}
ll t=0;
a[0]=1;
for(int i=1;i<=7;i++) {
a[i]=a[i-1]*10;
}
for(int i=1;i<=n;i++) {
t=i-1;
int j;
for(j=1;j<=7;j++) {
t=t*10%n;
if((i-t+n)%n<a[j]) break;
}
ans+=j;
}
printf("%d\n",ans);
return 0;
}
D Jobs (Easy Version)
题目
n个公司，每个公司有p个岗位，有对应的IQ、EQ、AQ要求，只要满足其中一个要求，即可获得offer。有q个朋友，问分别受到几个offer。
分析
动态规划
对于指IQ为i,EQ为j，对AQ的最低要求
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int N=405,M=5e5+5;
int n,q,seed;
int f[11][N][N];
int a[20];
ll t=0;
ll qsm(int a,int b) {
ll ans=1;
while(b) {
if(b&1) ans=ans*a%mod;
a = 1ll*a*a%mod;
b>>=1;
}
return ans;
}
int solve(int x,int y,int z) {
int ans=0;
for(int i=1;i<=n;i++) {
ans+=(f[i][x][y]<=z);
}
return ans;
}
int main(){
//freopen("data.in","r",stdin);
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
cin>>n>>q;
int a,b,c,p;
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++) {
cin>>p;
for(int j=1;j<=p;j++) {
cin>>a>>b>>c;
f[i][a][b]=min(f[i][a][b],c);
}
}
cin>>seed;
for(int k=1;k<=n;k++) {
for(int i=1;i<N;i++) {
for(int j=1;j<N;j++) {
f[k][i][j]=min(f[k][i][j],f[k][i-1][j]);
f[k][i][j]=min(f[k][i][j],f[k][i][j-1]);
}
}
}
int lastans=0;
std::mt19937 rng(seed);
std::uniform_int_distribution<> u(1,400);
for (int i=1;i<=q;i++) {
int IQ=(u(rng)^lastans)%400+1; // The IQ of the i-th friend
int EQ=(u(rng)^lastans)%400+1; // The EQ of the i-th friend
int AQ=(u(rng)^lastans)%400+1; // The AQ of the i-th friend
lastans=solve(IQ,EQ,AQ); // The answer to the i-th friend
t=(t+qsm(seed,q-i)*lastans%mod)%mod;
}
printf("%lld",t);
return 0;
}
H Wall Builder II
题目
有n-i+1块长为i的砖块(1<=i<=n)，问拼成矩形的最小面积
分析
尽量让矩形的长宽相等，且由于小砖块较多，所以一定有解
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=1e3+7;
const int N=2e4+5,M=5e5+5;
int n,t,h;
int a[N];
void solve() {
memset(a,0,sizeof(a));
for(int i=n;i>=1;i--) {
for(int j=1;j<=n-i+1;j++) {
int p=0;
while(a[p]+i>t) {
p++;
}
printf("%d %d %d %d\n",a[p],p,a[p]+i,p+1);
a[p]+=i;
}
}
}
int main(){
//freopen("data.in","r",stdin);
//ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
int T;
cin>>T;
while(T--) {
cin>>n;
int area=0;
for(int i=1;i<=n;i++) {
area+=i*(n-i+1);
}
t=sqrt(area);
while(area%t!=0) t++;
h = area/t;
printf("%d\n",(t+h)*2);
solve();
}
return 0;
}
京公网安备 11010502036488号