A. Entry song
Danqing is brewed for thousands of years. Once drunk, it can relieve your worries.
A regretless youth is in vain, but wishes to be ambitious.
Matrix prefix and plus force \ (O(N^2M^2)\) 60pts can be done with hands
Observe the data range and guess that it should be to find an algorithm of \ (O(N^3) \). When you think of the previous question, it should be \ (N^2 \) and \ (N \) to process a sequence of answers. Then, there is no then
For a sequence, how to \ (O(N) \) solve when the sum of sub segments is a multiple of k,
Considering the prefix sum, if the sum of a sub segment is a multiple of k, then the left and right bounds of the sub segment are congruent in the sense of module k. open array records, \ (s[i] \) indicates that there are several prefixes and the remainder of module k is I, and any two correspond to a legal matrix, so you can cut off this problem happily. Another point is that the initial value of \ (s[0] \) should be set to 1, The direct reason why the modulus k is 0 is the legal matrix.
Remember to open longlong, and don't memset every time, otherwise you will like to mention that TLE35 is not as good as violence
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=405;
int n,m,k;
int mp[maxn][maxn];
long long sum[maxn][maxn];
int s[1000005];
int main()
{
freopen("rally.in","r",stdin);
freopen("rally.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&mp[i][j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mp[i][j];
long long ans=0;
for(int i=1;i<=n;++i)
for(int x=i;x<=n;++x)
{
s[0]=1;
for(int j=1;j<=m;++j){
long long w=(sum[x][j]-sum[i-1][j])%k;
ans+=s[w];s[w]++;
}
for(int j=1;j<=m;++j){
long long w=(sum[x][j]-sum[i-1][j])%k;
s[w]--;
}
}
printf("%lld\n",ans);
return 0;
}
B. General order
History falls into the hands of winners, at least we have legends
Who says that losers cannot be immortal, and fists can only make people bow their heads
Thought can make people look up, look up, love and chase
The dream in your heart
I'm the only one who plays DP. There's no problem with my thinking, but I hung up A bunch of details and adjusted them for more than an hour. The result is only 20pts, and then I changed A little detail A
It can be found from the drawing that the child node may not only contribute to the parent node, but also need the parent node to contribute during the transfer. Let \ (g[x][i] \) represent the minimum scheme that the distance that the child tree with X as the root can stay is I. during the transfer, we need to know \ (g[v][j]\)(v is the child node of X, \ (j \in [-k,k] \)). In order to deal with the case of negative subscript, I uniformly add 21, You can also add K like the solution of the valley problem.
Consider the specific process (Please add a constant to the subscript of the specific code)
If it is a leaf node, then \ (g[x][i]=0\;(i\in [-k,-1]) g[x][i]=1\;(i\in [0,k])\)
General transfer
Preprocessing \ (ls[i] \) records the sum of schemes with the garrison distance of x subtree as I
If you are stationed at x, the child node can contribute - K \ (g[x][k]=ls[-k]+1 \)
If x has a positive contribution I, but is not stationed in X, then one child node must contribute i+1, and other child nodes contribute - I \ (g[x][i]=min(g[v][i+1]+ls[-i]-g[v][-i])i\in[0,k) \)
If x has a negative contribution I, then all child nodes contribute i+1 to ensure legitimacy \ (g[x][i]=ls[i+1]i\in[-k,-1] \)
Since some states do not actually exist, it is obviously unreasonable to have \ (g [x] [i] > g [x] [J] (I < J) \), so it is necessary to take \ (min \), that is \ (g[x][i]=min(g[x][i],g[x][i+1]) \, which ensures that the smaller I is, the smaller g is and legal
dp ends here, and then we'll briefly talk about the positive solution
Consider giving up DP. You can be greedy, find a root casually, and then find the deepest point. The k-level ancestors stationed at this point must be the best. They are sorted according to the point depth from large to small. Each time, take the deepest point to check whether it is controlled. If not, garrison the k-level father or root node and update the surrounding points violently.
Attached dp code
#include<cstdio>
#include<cstring>
using namespace std;
int min(int x,int y){return x<y?x:y;}
const int maxn=100005;
const int inf=1047483647;
struct edge{
int to,net;
}e[maxn<<1|1];
int head[maxn],tot,n,k,t;
void add(int u,int v){
e[++tot].net=head[u];
head[u]=tot;
e[tot].to=v;
}
int g[maxn][55];
int ls[55];
void print(){
puts("");
for(int i=1;i<=n;++i){
for(int j=21-k;j<=21+k;++j)
printf("%d ",g[i][j]);
puts("");
}
}
void work(int x,int fx){
bool flag=1;
for(int i=head[x];i;i=e[i].net){
int v=e[i].to;if(v==fx)continue;
work(v,x);flag=0;
}
if(flag){
for(int i=21-k;i<21;++i)g[x][i]=0;
for(int i=21;i<=21+k;i++)g[x][i]=1;
return;
}else{
for(int i=21-k;i<=21+k;++i)ls[i]=0;
for(int i=head[x];i;i=e[i].net){
int v=e[i].to;if(v==fx)continue;
for(int j=21-k;j<=21+k;++j)ls[j]+=g[v][j];
}
for(int i=head[x];i;i=e[i].net){
int v=e[i].to;if(v==fx)continue;
for(int j=0;j<k;++j)
g[x][j+21]=min(g[x][j+21],g[v][j+22]+ls[21-j]-g[v][21-j]);
}
for(int i=1;i<=k;++i)g[x][21-i]=ls[21-i+1];
g[x][k+21]=ls[21-k]+1;
for(int i=k+21-1;i>=21-k;--i)g[x][i]=min(g[x][i],g[x][i+1]);
}
//print();
}
int main()
{
freopen("general.in","r",stdin);
freopen("general.out","w",stdout);
scanf("%d%d%d",&n,&k,&t);
for(int i=1;i<n;++i){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
if(k==0){printf("%d\n",n);return 0;}
else{
memset(g,1,sizeof(g));
work(1,0);
printf("%d\n",g[1][21]);
}
return 0;
}
C. Starry sky
If fate steals only the result, time steals the original intention, only the hardship.
You came, and then you left, leaving only the stars.
This question is very divine...
The examination room didn't have time to play T3 because of adjusting T2, and finally output 2 cheated 12pts
Search for a similar breakup is the question of wish. It's about 72pts. Damn it
The positive solution requires ingenious transformation of 100 million points
First, use 01 to indicate whether the light is on or off, and then maintain the difference \ (cf[i]=a[i]\;xor\;a[i-1] \) of a prefix in a way similar to the prefix sum. Note that the maximum I should be n+1
Each operation is equivalent to reversing two numbers. The ultimate goal is to make the whole sequence become 0
This is it.
First conversion:
For a given 0 1 sequence of numbers, each time we reverse two numbers as required, asking at least once can make the sequence all become 1
When you think about the problem of breaking up, or simply think about it, you can find that there must be at least one 1 in each operation. If you operate two 1's, they will all become 0. If you operate one 1 and one 0, it is equivalent to exchanging their positions. There are at most 16 1's and the positions are known, so there are
Second transformation
Give you a few points and move one of them a specific distance at a time. If the two points touch each other, the two points disappear together.
Ask how to move to minimize the number of steps to eliminate all points.
So, to run the shortest path, I used a dead algorithm to get the minimum number of steps to eliminate any two 1s, and the problem can be further transformed
The third transformation
Give you a pile of items. You can only take out a given pair of items at a time. Taking out different pairs of items has different costs. Ask how to take out items to minimize the cost.
There are only 16 items, which can be pressed in shape
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
int flag[40005],cf[40005];
int n,k,m,op[67],x[19],cnt;
int dis[21][40005];
bool vis[40005];
queue<int>q;
void spfa(int now,int nowx){
memset(vis,0,sizeof(vis));
q.push(nowx);dis[now][nowx]=0;
while(!q.empty()){
int y=q.front();q.pop();vis[y]=0;
for(int i=1;i<=m;++i)
{
int v=y+op[i],u=y-op[i];
if(v<=n+1){
if(dis[now][v]>dis[now][y]+1){
dis[now][v]=dis[now][y]+1;
if(!vis[v]){q.push(v);vis[v]=1;}
}
}
if(u>0){
if(dis[now][u]>dis[now][y]+1){
dis[now][u]=dis[now][y]+1;
if(!vis[u]){q.push(u);vis[u]=1;}
}
}
}
}
}
int f[67737];
void dp(){
memset(f,0x3f,sizeof(f));
f[(1<<cnt)-1]=0;
for(int i=(1<<cnt)-1;i;--i){
for(int j=1;j<=cnt;++j){
if(!((1<<(j-1))&i))continue;
for(int k=j+1;k<=cnt;++k){
if(!((1<<(k-1))&i))continue;
int s=~((~i)|(1<<(j-1))|(1<<(k-1)));
f[s]=min(f[s],f[i]+dis[j][x[k]]);
}
}
}
printf("%d\n",f[0]);
}
int main()
{
freopen("starlit.in","r",stdin);
freopen("starlit.out","w",stdout);
scanf("%d%d%d",&n,&k,&m);
for(int i=1;i<=k;++i){int a;scanf("%d",&a);flag[a]=1;}
for(int i=1;i<=m;++i)scanf("%d",&op[i]);
for(int i=1;i<=n+1;++i)cf[i]=flag[i-1]^flag[i];
for(int i=1;i<=n+1;++i)if(cf[i])x[++cnt]=i;
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=cnt;++i)spfa(i,x[i]);
dp();
return 0;
}