It was a bad game. It was an iron fight. After the game, it was almost filled with a silver medal (silver is faster than hand speed). It was really too little experience. Come on!
J. Justifying the Conjecture
( Question: Ask if a number can be broken down into one \(x\) and one \(y\) so that \(x\) is prime and \(y\) is a total.
( Solution: Check-in questions, for even numbers greater than 2 can obviously be split into 2+an even number, odd numbers greater than 5 can be split into 3+an even number, other special judgments on the line.
K.Keeping Rabbits
( Topic: n numbers, the probability of each number increasing is \(\frac{a_i}{\Sigma_j}\), ask the expectation of each number i n k days
( Question: It's easy to know that the expected growth of each number is fixed every day (proportionally), so all you need to do is add \(frac{ka_i}{\Sigma_j}\) to each number.
( In fact, this question can directly observe the data for two days and guess the result directly, which can save time.
F.Fixing Banners
( Title: Six strings in which you can pick any letter and ask if you can spell the selected letters into "harbin"
( Solution: Direct processing of six letters of h,a,r,b,i,n i n six strings. Violent enumeration of the letters selected for each string or pressure dp can be resolved.
( Checking in imagination is also a talent in the competition, and the compiler will only be effective if it compiles and debugs!!! (wastes half an hour to find the output error result is not compiled)
I.Interesting Permutation
( Meaning: For an array \(a[i]\), define \(f[i]\) as the maximum number of the first i, \(g[i]\) as the minimum number of the first i, \(h[i]=f[i]-g[i]\), and now give \(h[i]\), ask for the possible alternatives to \(a[i]\).
( Solution: Consider the relationship between \\(h[i]\\\\\(h[i]\\\\\neq h[i-1]\\[i]]\\\\\\\neq h[i-1]\\\\\\\Drop one.
( The examination ground was too obsessed with using violence to draw a beautiful conclusion. In fact, it can be deduced by division of labor, some people write violence and some people think about mathematical deduction. Moreover, in mathematical derivation, I have always been obsessed with the study of intervals with the same value of \(h[i]\), but I have not tried to classify each point into intervals. Also, there is no clear way to think about the problem and modify the original code directly (you should back up the original code and copy and paste the available code to help refactoring). We made several serious mistakes on the examination ground:
- Each set of data is return ed before it has been read. You can read and process the data later
- Data Range Issue: long long is ACMer's pain
We can only say that we have insufficient experience in problem-solving, insufficient team integration and more intensive training.
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int t,h[100005],n;
const int MOD=1000000007;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&h[i]);
if(h[1]!=0||h[n]!=n-1) {puts("0"); return ;}
int sum=0;LL ans=1;
for(int i=2;i<=n;i++)
{
if(h[i]<h[i-1]) {puts("0"); return ;}
if(h[i]==h[i-1]) {ans=(ans*sum)%MOD;sum--;}
else {sum+=h[i]-h[i-1]-1; ans=(ans*2)%MOD;}
}
printf("%lld\n",ans);
return ;
}
int main()
{
cin>>t;
while(t--)
solve();
return 0;
}
E. Exchanging Gifts
( Idea: Find out the maximum number of possible positions for an array that are different from the original array for values at the same location after the exchange order. There are two representations of arrays, one is given directly, and the other is the connection of the first two arrays.
( Question (what I do): First consider any array that can be given directly. In fact, this result is only related to the number of elements that occur most often. If it is not half as large as the length of the array \(len\), the answer must be \(len\), otherwise the result can be deduced \(2*(len-maxcnt)\). We only need to count the number of elements that require the array to be present the most. By pushing down from \(n\) to \(1\) like a segment tree, you can break down \(s_n\) into a combination of directly given arrays and directly find out the number of all elements of \(s_n\). Read-in optimization is required here.
( I find that there is a really big gap between reading and reading. Within this data range, optimized fast reading is six times faster than unoptimized fast reading, and scanf is even more miserable. Also, I've been doing poorly in detail before. Although memset is fast, it still seems to be a waste of time when there is a lot of data, not as fast as for loop reset. I used to think complexity was okay, cards were often useless, so I think it's time to change that.
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
map <int,LL> mp[1000006];
LL cnt[1000006];
int rel[1000006][3],ch[1000006],n;
inline void push_down(int x)
{
if(ch[x]==1) return ;
cnt[rel[x][1]]+=cnt[x],cnt[rel[x][2]]+=cnt[x],cnt[x]=0;
}
LL getans(int x)
{
LL mcnt=-1,len=0;
for(auto [x,y]: mp[x])
{
mcnt=max(mcnt,y);
len+=y;
}
if(mcnt<=len/2) return len;
else return 2*(len-mcnt);
}
void sumn()
{
for(int i=1;i<n;i++)
if(cnt[i])
{
for(auto [x,y] :mp[i])
mp[n][x]+=y*cnt[i];
}
}
inline char nc() {
static char buf[1000000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <class T> inline bool input(T &x) {
x = 0; char c = nc(); bool f(0);
while (c < '0' || c > '9') { if (c == EOF) return false; f = c == '-', c = nc(); }
while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = nc(); if (f) x = -x; return true;
}
void solve()
{
int cntt,tmp;
input(n);
for(int i=1;i<=n;i++)
{
input(ch[i]);
if(ch[i]==1)
{
input(cntt);
for(int j=1;j<=cntt;j++)
{
input(tmp);
mp[i][tmp]++;
}
}
else input(rel[i][1]),input(rel[i][2]);
}
cnt[n]=1;
for(int i=n;i;i--)
push_down(i);
sumn();
printf("%lld\n",getans(n));
for(int i=1;i<=n;i++)
mp[i].clear();
memset(cnt,0,sizeof(cnt));
return ;
}
int main()
{
int t;
input(t);
while(t--)
solve();
return 0;
}