UOJ Round #1
http://vfleaking.blog.uoj.ac/blog/33
「UR #1」缩进优化
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll tot,ans_mx; int n,mx; int a[1000005],s[1000005]; int main() { n=read(); for(int i=1;i<=n;i++) { a[i]=read(); mx=max(mx,a[i]); tot+=a[i]; } for(int i=1;i<=n;i++)s[a[i]]++; for(int i=1;i<=mx;i++)s[i]+=s[i-1]; for(int i=2;i<=mx;i++) { ll ans=0; for(int j=i;j<=mx;j+=i) { if(j+i-1>mx)ans+=(s[mx]-s[j-1])*(j/i); else ans+=(s[j+i-1]-s[j-1])*(j/i); } ans_mx=max(ans_mx,ans*(i-1)); } printf("%lld\n",tot-ans_mx); return 0; } |
「UR #1」外星人
这题似乎没那么麻烦
f[i][j]表示前i大的，得出的结果为j的方案数
第i大的可以在当前视之生效，也可以放在剩下n-i个任意一个的后面使之不生效
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 998244353 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,x; int a[1005]; ll f[1005][5005]; bool g[1005][5005]; int main() { n=read();x=read(); for(int i=1;i<=n;i++)a[i]=read(); sort(a+1,a+n+1,greater<int>()); f[0][x]=1;g[0][x]=1; for(int i=1;i<n;i++) { for(int j=0;j<=x;j++) { (f[i][j%a[i]]+=f[i-1][j])%=mod; g[i][j%a[i]]|=g[i-1][j]; } for(int j=0;j<=x;j++) { (f[i][j]+=f[i-1][j]*(n-i))%=mod; g[i][j]|=g[i-1][j]; } } for(int j=0;j<=x;j++) (f[n][j%a[n]]+=f[n-1][j])%=mod,g[n][j%a[n]]|=g[n-1][j]; for(int i=x;i>=0;i--) if(g[n][i]) { printf("%d %lld\n",i,f[n][i]);break; } return 0; } |
「UR #1」跳蚤国王下江南
什么。。仙人掌毁灭世界。？
这个大坑估计不会填了
计数器 9787221
OI 课件=>
OI 课件=>
不，是跳蚤大战仙人掌23333333(#滑稽）
orzorz
省队爷开始屠UR了，Orz