T1签到题
题面
Description
给定\(n\)个数，求出这\(n\)个数的一个非空子集，使得这个子集中的数的和能被\(n\)整除，无解输出\(-1\).
Input
第一行为数据组数\(T\)
接下来\(T\)组数据，每组数据第一行为一个正整数\(n\)，第二行为\(n\)个用空格分开的数。
Output
对于每一组数据，如果无解输出一行一个整数-1；否则第一行输出一个正整数m，表示子集的大小，然后在第二行输出m个数，分别是这个子集中的数。如果有多种方案，输出任意一种。
Sample Input
1
1
1
Sample Output
1
1
Data Constraint
对于\(30\%\)的数据 \(n\le 20\)
对于\(50\%\)的数据 \(n\le100\)
对于\(70\%\)的数据 \(n\le1000\)
对于\(100\%\)的数据 \(n\le100000,T\le10\)
题解
记\(s\)数组为\(a\)数组的模\(n\)下的前缀和。由抽屉原理，所以\(s_0,s_1,s_2,\cdots,s_n\)中在模\(n\)的前提下必有两个数相等，必有解，所以必有一段连续的\(a\)的和模\(n\)为\(0\)。我们只需要求出两个相同的\(s_i\)和\(s_j\)即可，我的代码时间复杂度为\(\Theta(Tn\log n)\)
code
#include<bits/stdc++.h>
#define rg register
#define fre(x)freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
typedef long long LL;
typedef long double LD;
typedef double db;
typedef unsigned long long uLL;
const db Pi=acos(-1);
vector<int> ans;
int a[100005],T,n,s[100005],id[100005];
bool cmp(int x,int y){return s[x]<s[y];}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
s[i]=(s[i-1]+a[i]%n+n)%n;
id[i]=i;
}id[++n]=0;
sort(id+1,id+n+1,cmp);
for(int i=1;i<n;i++)
if(s[id[i]]==s[id[i+1]]){
int l=id[i],r=id[i+1];
if(l>=r)swap(l,r);
printf("%d\n",r-l);
for(int i=l+1;i<=r;i++)
printf("%d ",a[i]);
break;
}
putchar(10);
}
return 0;
}
T2邮局选址
题面
Description
在 J 市的一条笔直的公路旁分布着 n 个村庄，每个村庄都有一个唯一的坐标 Xi，任意一对村庄的坐标不同。最近，J 市领导计划在村庄里新建 m 个邮局，而邮局在 n个村庄里的分布情况会影响到居民的便利程度。
设 m 个邮局分别建在 P1,P2,..,Pm 号村庄。每个村庄的村民都会找到与其距离最近的一个邮局，若有多个距离最近的则会任选一个，该村庄的便利度即为该村庄与其最近的邮局的距离，而所有村庄的便利度的和即为总便利度。
严格地讲，总便利度 C定义为Σmin{|Xi-XPj| (1≤j≤m)}
现在，由你来安排邮局的建设位置。请计算最小的 C 是多少。
Input
第一行两个整数 n m
第二行递增的n 个整数，表示 X1..Xn
Output
一行一个整数，表示最小的 C
Sample Input
10 5
1 2 3 6 7 9 11 22 44 50
Sample Output
9
Data Constraint
对于30%的测试数据 n ≤ 10
对于60%的测试数据 n ≤ 50
对于100%的测试数据 1 ≤ n ≤ 300; 1 ≤ m ≤ 30; m ≤ n; 1 ≤ Xi ≤ 10000
Hint
样例解释：建立在坐标为：2 7 22 44 50的位置
每个村庄的便利度分别为：1 0 1 1 0 2 4 0 0 0
题解
显然这些点肯定是放在村庄上的，所以动态规划，我们设状态\(f_{i,j}\)为前\(i\)个村庄，放\(j\)个邮局，且第\(i\)个村庄放邮局。方便转移我们预处理出一个数组\(w_{i,j}\)表示在\(i,j\)区间里只在第\(i\)和第\(j\)个村庄修建邮局，\(i\)到\(j\)这几个村庄的便利度是多少，我们可以写出转移方程。
\[f_{i,j}=\min_{0\le k<i}(f_{k,j-1}+w_{k,i}) \]答案为\(f_{n+1,m+1}\)，我在两端分别加了一个邮局，另外预处理即可，时间复杂度为\(\Theta(n^3+n^2m)\)。
code
#include<bits/stdc++.h>
#define rg register
#define fre(x)freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
typedef long long LL;
typedef long double LD;
typedef double db;
typedef unsigned long long uLL;
const db Pi=acos(-1);
LL w[305][305],x[305],f[305][35];
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&x[i]);
sort(x+1,x+n+1);
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
w[0][i]+=x[i]-x[j];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
w[i][n+1]+=x[j]-x[i];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
for(int k=i+1;k<j;k++)
w[i][j]+=min(x[k]-x[i],x[j]-x[k]);
memset(f,27,sizeof(f));f[0][0]=0;
for(int i=1;i<=n+1;i++)
for(int j=1;j<=m+1;j++){
for(int k=0;k<i;k++)
f[i][j]=min(f[i][j],f[k][j-1]+w[k][i]);
}
printf("%lld",f[n+1][m+1]);
return 0;
}
T3分数
题面
Description
在一门叫做计算机应用数学的神奇的课上，老师教给大家如何处理小数的进制转换：
p进制的小数abc.def的十进制值为： a*p2+b*p+c+d/p+e/p2 +f/p^3 。
例如十进制数 1/3 在十进制下小数表示为0.33333…，在三进制下为0.1，在三十进制下为0.A。（这里A的含义与十六进制中A的含义相同，均表示10）。
下课后，老师要求kAc将N个十进制的分数写成k进制下的小数。然而kAc发现，很多十进制分数根本不可能写成有限的k进制小数！这令他十分不爽，不过他想知道，最小需要几进制才能使得这些十进制分数在该进制下均为有限的小数。
Input
第一行一个整数N
接下来N行，每行两个整数a, b，表示一个十进制小数a/b 。
Output
一个整数，表示最小进制数。这里，请按照十六进制输出，所有字母全部大写。（例如，如果答案为十进制下26，则输出1A）。
Sample Input
3
3 99
1 99
1 11
Sample Output
21
Data Constraint
对于20%的测试数据：n=1
对于50%的测试数据：n<=10，a, b <= 10000，保证最终答案在十进制下不超过10000。
对于70%的测试数据：n<=100，a, b<= 10000。
对于100%的测试数据：n<=1000，1 <= a,b <= 1000000000。
Hint
样例解释：
在33进制下，3/99可以表示为0.1，1/99可以表示为0.0B，1/11可以表示为0.3。
可以证明不存在更小的进制，使得他们均为有限小数。
题解
由于\(A\)最多只有一个大于\(\sqrt{A}\)的质因子，所以我们可以把小于\(\sqrt A\)的处理出来，再把剩下的取个重，然后乘起来就行了，注意使用高精度，时间复杂度\(\Theta(n\sqrt{b_{max}})\)。
code
#include<bits/stdc++.h>
#define rg register
#define fre(x)freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
typedef long long LL;
typedef long double LD;
typedef double db;
typedef unsigned long long uLL;
const db Pi=acos(-1);
const int N=1e5;
int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);}
int a[1005],b[1005],pr[100005],cnt;
bitset<100005> flag;
void init(){
for(int i=2;i<=N;i++){
if(!flag[i])pr[++cnt]=i;
for(int j=i+i;j<=N;j+=i)
flag[j]=1;
}
flag=0;
}
LL ans[100005];
int len=1;
void Times(int w){len+=15;
for(int i=1;i<=len;i++)ans[i]*=w;
for(int i=1;i<=len;i++)
ans[i+1]+=ans[i]/16,ans[i]%=16;
while(ans[len]==0)len--;
}
int main(){
init();
int n;scanf("%d",&n);
for(int i=1,g;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
g=gcd(a[i],b[i]);
a[i]/=g,b[i]/=g;
for(int j=1;j<=cnt&&b[i]>1;j++)
while(b[i]%pr[j]==0)
b[i]/=pr[j],flag[j]=1;
}
ans[1]=1;
sort(b+1,b+n+1);
n=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=cnt;i++){
if(!flag[i])continue;
Times(pr[i]);
}
for(int i=1;i<=n;i++)Times(b[i]);
for(int i=len;i;i--){
if(ans[i]<10)printf("%d",ans[i]);
else printf("%c",ans[i]-10+'A');
}
return 0;
}
T4有间医院
题面
Description
从前有家医院，医院里有n个医生，分到4个组。每天进行医护工作时，每个组的医生都会有变动。每个医生都有一个特定的编号，而且都能分去4个组中的任意一个。
在第一天，当医院开门时，医生会被按顺序分到四个组里面。如果这四个组的医生数目分别为g1, g2, g3, g4，那么分组方案会如下所示：
第1组： 1, 2, …, g1
第2组： g1+1, g1+2, …, g1+g2
第3组： g1+g2+1, g1+g2+2, …, g1+g2+g3
第4(0) 组： g1+g2+g3+1, g2+g2+g3+2, …, g1+g2+g3+g4
然后，第一个病人会选择医生1，就诊结束后，医生1会被分到第2组的最后一个位置。第二个病人会选择医生g1+1，就诊结束后，医生g1+1会被分到第3组的最后一个位置……依次类似，第k个病人会选择第k%4组的第1个医生，就诊结束后，这个医生会被分到第(k+1)%4组的最后一个位置上。
这间医院一天要处理m个病人。而且，在第二天开始前，这些医生会根据上一天最后的情况再进行编排。他们会把四个组首尾相接合并在一起，然后再重新按g1, g2, g3, g4来分组安排。
例如，如果某天结束后的分组情况如下所示：
第1组：d1,d2,....,d(k1) 第2组:d(k1+1),d(k1+2),.....,d(k2)
第3组：d(k2+1),d(k2+2),...,d(k3)第4组：d(k3+1),d(k3+2),...,d(k4)
合并后，变成：d1,d2,....,d(k1),d(k1+1),d(k1+2),.....,d(k2),d(k2+1),d(k2+2),...,d(k3),d(k3+1),d(k3+2),...,d(k4)
最后，重新按g1, g2, g3, g4分组变成：
第1组：d1,d2,...,d(g1)
第2组：d(g1),d(g1+1),...,d(g1+g2)
第3组：d(g1+g2+1),d(g1+g2+2),...,d(g1+g2+g3)
第4组：d(g1+g2+g3+1),d(g1+g2+g3+2),...,d(g1+g2+g3+g4)
然后新的一天又开始了，和第一天一模一样地继续处理新的病人。
过了一些天后，我们会发现一个有趣的理解：医生的分组安排居然和第1天一模一样！你能告诉我这是第几天吗？
Input
输入包含多组数据。
对于每组数据，仅一行，包含五个整数g1，g2，g3，g4，p（1<=g1,g2,g3,g4<=20,p<=10000），分别表示第1组，第2组，第3组，第4组的人数，以及每天的病人数。
当这五个整数都是0时表示输入结束。
Output
对每组数据输出一行，表示在这天的时候医生的分组安排会和第1天一样。答案保证不会超过32位整数范围。
Sample Input
2 1 1 1 6
0 0 0 0 0
Sample Output
3
Hint
【样例解释】
第一天开始前的分组： g1: 1 2 g2:3 g3:4 g4:5
第1个病人之后： g1:2 g2:3 1 g3:4 g4:5
第2个病人之后： g1:2 g2:1 g3:4 3 g4:5
第3个病人之后： g1:2 g2:1 g3:3 g4:5 4
第4个病人之后： g1:2 5 g2:1 g3:3 g4:4
第5个病人之后： g1:5 g2:1 2 g3:3 g4:4
第6个病人之后： g1:5 g2:2 g3:3 1 g4:4
第一天结束后，分组情况是： g1: 5 2 g2:3 g3:1 g4:4
第二天结束后，分组情况是： g1:4 2 g2:3 g3:5 g4:1
第三天结束后，分组情况是： g1:1 2 g2:3 g3:4 g4:5
【数据说明】
对于50%的数据，每个文件的数据组数不超过100。
对于100%的数据，每个文件的数据组数不超过10000。
题解
这题没什么好说的，只需要模拟一天，连边然后看环长求最小公倍数即可，复杂度\(\Theta(g1+g2+g3+g4+P)\)。
code
#include<bits/stdc++.h>
#define rg register
#define fre(x)freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
typedef long long LL;
typedef long double LD;
typedef double db;
typedef unsigned long long uLL;
const db Pi=acos(-1);
struct Edge{int Nxt,To;}Ed[105];
int Head[105],Cnt;
void Add(int u,int v){
Ed[++Cnt]=(Edge){Head[u],v};
Head[u]=Cnt;
}
bool vis[105];
int len;
void Dfs(int u){
vis[u]=1;len++;
for(int i=Head[u];i;i=Ed[i].Nxt)
if(!vis[Ed[i].To])Dfs(Ed[i].To);
}
deque<int> flag[5];
LL gcd(LL a,LL b){return (b==0)?a:gcd(b,a%b);}
int main(){
int g1,g2,g3,g4,p;
while(scanf("%d%d%d%d%d",&g1,&g2,&g3,&g4,&p)!=EOF){
memset(vis,0,sizeof(vis));
memset(Head,0,sizeof(Head));Cnt=0;
if(!g1&&!g2&&!g3&&!g4&&!p)break;
for(int i=1;i<=g1;i++)flag[1].push_back(i);
for(int i=g1+1;i<=g1+g2;i++)flag[2].push_back(i);
for(int i=g1+g2+1;i<=g1+g2+g3;i++)flag[3].push_back(i);
for(int i=g1+g2+g3+1;i<=g1+g2+g3+g4;i++)flag[4].push_back(i);
for(int i=1;i<=p;i++){
int u=flag[(i-1)%4+1].front();
flag[(i-1)%4+1].pop_front();
flag[i%4+1].push_back(u);
}
if(flag[1].size()<g1){
int u=flag[2].front();
flag[2].pop_front();
flag[1].push_back(u);
}
if(flag[2].size()<g2){
int u=flag[3].front();
flag[3].pop_front();
flag[2].push_back(u);
}
if(flag[3].size()<g3){
int u=flag[4].front();
flag[4].pop_front();
flag[3].push_back(u);
}
for(int i=0;i<g1;i++){
int u=flag[1].front();
Add(u,i+1),flag[1].pop_front();
}
for(int i=g1;i<g1+g2;i++){
int u=flag[2].front();
Add(u,i+1),flag[2].pop_front();
}
for(int i=g1+g2;i<g1+g2+g3;i++){
int u=flag[3].front();
Add(u,i+1),flag[3].pop_front();
}
for(int i=g1+g2+g3;i<g1+g2+g3+g4;i++){
int u=flag[4].front();
Add(u,i+1),flag[4].pop_front();
}
int ans=1;
for(int i=1;i<=g1+g2+g3+g4;i++)
if(!vis[i]){
len=0;Dfs(i);
ans=1ll*ans*len/gcd(ans,len);
}
printf("%d\n",ans);
}
return 0;
}