A Alphabet Cake
给一个R*C矩阵，里面有大写字母和？（大写字母每个最多出现一次），用矩阵中出现的大写字母填满矩阵，要求每个字母出现的区域都恰为一子矩阵。
直接把每个字母向行延展，后向列延展。
#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int k;
char s[100][100];
int a[10000];
int f[100][100];
bool b[10000];
int main()
{
freopen("A.in","r",stdin);
freopen("a.out","w",stdout);
int T=read();
For(kcase,T) {
printf("Case #%d:\n",kcase);
int n,m;
cin>>n>>m;
For(i,n) cin>>(s[i]+1);
MEM(b);
For(i,n) {
int j=1;
while(j<=m&&s[i][j]=='?') ++j;
if (j<=m) {
For(k,j) s[i][k]=s[i][j];
Fork(k,j+1,m) if (s[i][k]=='?') s[i][k]=s[i][k-1];
} else {
b[i]=1;
}
}
int i=1;
while(b[i]) ++i;
For(j,i-1) strcpy(s[j]+1,s[i]+1);
Fork(j,i+1,n) if (b[j]) strcpy(s[j]+1,s[j-1]+1);
For(i,n) cout<<(s[i]+1)<<endl;
}
return 0;
}
B Ratatouille
给n种调料，每种m包，每包有一个重量Qij，已知一个固定比例的配方，问最多能凑出多少份该配方？
k(r1,r2,⋯,rn),k是整数，ri可调整10%
贪心，每次贪最小的k，然后查找是否有合法解，若有把最小的n个拿走
#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
ll read()
{
ll x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
ll p[MAXN],a[MAXN][MAXN];
ll c[MAXN];
bool b[MAXN][MAXN];
int main()
{
freopen("B.in","r",stdin);
// freopen("B2.out","w",stdout);
int T=read();
For(kcase,T) {
printf("Case #%d: ",kcase);
ll n,m,ans=0;
cin>>n>>m;
For(i,n) cin>>p[i];
For(i,n) For(j,m) {
cin>>a[i][j];
}
For(i,n) sort(a[i]+1,a[i]+1+m);
MEM(b)
ll k=1;while(1) {
ll fl=0,cnt=0;
memset(c,-1,sizeof(c));
For(i,n) {
double mi=(double)p[i]*k*0.9,mx=(double)p[i]*k*1.1;
For(j,m) if (!b[i][j]) {
if (mi<=a[i][j]&&a[i][j]<=mx) {
c[i]=j;
++cnt;break;
}
}
if (mi>a[i][m]) fl=1;
}
if (cnt==n) {
For(i,n) b[i][c[i]]=1;
++ans;
} else ++k;
if (fl) break;
}
cout<<ans<<endl;
}
return 0;
}
C Play the Dragon
You’ve discovered it: the ultimate recipe for ratatouille, the famous French dish! You know which ingredients to use, and how many grams of each one to use, in order to make one serving of ratatouille. But you believe that anyone can cook, and so you want to share the recipe with the world… and make some money in the process!
You have ordered some ingredient packages that are easy to ship. Each package contains some amount of one ingredient; different packages may have different amounts even if they contain the same ingredient. For convenience, you ordered the same number of packages of each ingredient.
You would like to use these packages to form as many ratatouille kits as possible to send to customers. A kit consists of exactly one package of each ingredient, and a label with the integer number of servings of ratatouille that the kit makes. Since you do not want to shortchange customers or waste food, each package must contain between 90 and 110 percent (inclusive) of the amount of that ingredient that is actually needed to make the number of servings of ratatouille on the kit’s label.
For example, suppose that one serving of ratatouille takes 500 g of tomato and 300 g of onion. Suppose that you have a 900 g package of tomato and a 660 g package of onion. You could form these into a kit that makes two servings of ratatouille. To make two servings, 1000 g of tomato and 600 g of onion are required. Since the 900 g of tomato you have is within [90, 110]% of the 1000 g of tomato required, and the 660 g of onion you have is within [90, 110]% of the 600 g of onion required, this is acceptable. However, you could not say that the kit makes one or three servings of ratatouille, nor could you say that it makes 1.999 servings (the number of servings must be an integer).
Note that there are some sets of packages that could never form a kit. Continuing with our recipe above, if you have a 1500 g package of tomato and an 809 g package of onion, for example, there is no amount of servings that you can make. Three servings would take 1500 g of tomato and 900 g of onion, and the amount of onion is not within the [90, 110]% range. No other integer amount of servings works, either.
You want to share your recipe with as many customers as possible, so you want to produce the maximum number of valid kits. (Of course, each package can be used in at most one kit.) What is the largest number of kits that you can form? Note that you are not required to maximize the total number of servings of ratatouille formed.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each case consists of the following:
One line with two integers N: the number of ingredients, and P, the number of packages of each ingredient.
One line with N integers Ri. The i-th of these represents the number of grams of the i-th ingredient needed to make one serving of ratatouille.
N more lines of P integers each. The j-th value on the i-th of these lines, Qij, represents the quantity, in grams, in the j-th package of the i-th ingredient.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of kits you can produce, as described above.
Limits
1 ≤ T ≤ 100.
1 ≤ Ri ≤ 106, for all i.
1 ≤ Qij ≤ 106, for all i and j.
Small dataset
1 ≤ N ≤ 2.
1 ≤ P ≤ 8.
Large dataset
1 ≤ N ≤ 50.
1 ≤ P ≤ 50.
N × P ≤ 1000.
答案肯定为DDDD..BBBB…..AAAA…..
中间如果有必要+C
显然可以预处理处A+B的最小次数
然后枚举D的次数就行
这样只能过小数据
C-small
#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
//#deifne MAXN (5000000)
//int h1[MAXN],h2[MAXN],d3[MAXN];
//void bfs(int hd,int hk,int d) {
// int hea=1,tai=1;
// h1[1]=hd,h2[1]=hk,d3[1]=d;
// while(hea<=tai) {
// int n1=h1[hea],n2=h2[hea],n3=d3[hea];
// ++hea;
//
// }
//}
ll hd,ad,hk,ak,b,d;
ll anas=INF;
void calc(ll t,ll p) {
ll ans=0,nowak=ak,c=hd;
bool fl=0;
while(t) {
ll n2ak=max(0LL,nowak-d);
if (c-n2ak>0) fl=0,t--,nowak=n2ak,c-=n2ak;
else {
if (fl) return;
c=hd-nowak;fl=1;
}
if (c<0) return;
++ans;
if (nowak==0) break;
}
fl=0;
while(p) {
ll n2ak=nowak;
if (c-n2ak>0||p==1) fl=0,c-=n2ak,--p;
else {
if (fl) return;
fl=1,c=hd-nowak;
}
++ans;
}
anas=min(anas,ans);
}
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
int T=read();
For(kcase,T) {
printf("Case #%d: ",kcase);
cin>>hd>>ad>>hk>>ak>>b>>d;
ll p=INF;
Rep(j,1000) {
ll p2=j+ceil(hk/(double)(ad+j*b));
p=min(p,p2);
}
anas=INF;
Rep(i,100) calc(i,p);
if (anas==INF) puts("IMPOSSIBLE");
else cout<<anas<<endl;
}
return 0;
}