Missed opportunity++
Pass the exam
T1 found that it was a water problem, took a few pictures with violence, and then changed it to add a few special judgments
T2 is not very good. Looking at T3, I found that 60 points are easier to take. I took a look at T4. Isn't this a ternary ring? I suddenly wanted to write T4, so I opened the code and felt that the space was a little hanging, so I stuck
Change the map to unordered_map is the limit data 2s. I think it's okay, and then look at T3
T3 immediately wrote a \ (n^3 \) violence, thought about 60, and found that the limit data was 0.2. After careful thinking, it seemed to be \ (n^2\ln \), so it didn't matter
T2 wanted to be violent and found that they wouldn't. some of them got t points, so they didn't get points in the end
100 + 0 + 100 + 100 = 300, take a look at the three AK's
Master Ma \ (10:30\)AK, then start happy AKIOI...% It's over
T1. Stone consolidation
If there are positive and negative, then a scheme can be constructed so that all contributions are the sum of absolute values
All positive and all negative sacrifice the smallest absolute value into negative contribution. Pay attention to special judgment 1
The main reason is that the data range will prompt such a direct scanning method
#include <bits/stdc++.h>
using namespace std;
inline 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<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
signed main()
{
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
int t;cin>>t;
while(t--)
{
int n=read(),mi=1e9,ans=0,cnt=0;
if(n==1){printf("%d\n",read());continue;}
for(int i=1;i<=n;i++)
{
int x=read();ans+=abs(x);mi=min(mi,abs(x));
if(x>=0)cnt++;
}
if(cnt==n||cnt==0)printf("%d\n",ans-2*mi);
else printf("%d\n",ans);
}
return 0;
}
T2. Flip game
When I saw the prefix and suffix, I seemed to understand everything
Find the intersection of \ (n-1 \) rectangles and the intersection of suffixes before preprocessing, then enumerate which is not selected, and finally subtract the intersection of \ (n \)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=300050;
struct node{
int x,l,y,r;
inline bool ck()
{
if(x==0&&l==0&&r==0&&y==0)return 0;
else return 1;
}
inline int gett()
{
if(!ck())return 0;
return (y-x+1)*(r-l+1);
}
inline void print()
{
cout<<"x"<<x<<"l"<<l<<"y"<<y<<"r"<<r<<endl;
}
}a[N],b[N],c[N];
int p,q,n;
inline bool check(node p1,node p2)
{
if(p1.l>p2.l)swap(p1,p2);
if(p1.r<p2.l||p1.y<p2.x||p2.y<p1.x)return 0;
return 1;
}
inline node get(node p1,node p2)
{
if(!check(p1,p2))return (node){0,0,0,0};
return (node){max(p1.x,p2.x),max(p1.l,p2.l),min(p2.y,p1.y),min(p1.r,p2.r)};
}
inline node gan()
{
node pp=(node){1,1,(int)1e9,(int)1e9};
for(int i=1;i<=n;i++)
{
if(!check(a[i],pp))return (node){0,0,0,0};
pp=get(pp,a[i]);
}
return (pp.r==1e9)?(node){0,0,0,0}:pp;
}
signed main()
{
freopen("carpet.in", "r", stdin);
freopen("carpet.out", "w", stdout);
int T;cin>>T;
while(T--)
{
memset(b,0,sizeof(b));memset(c,0,sizeof(c));
scanf("%lld%lld%lld",&p,&q,&n);
for(int i=1;i<=n;i++)scanf("%lld%lld%lld%lld",&a[i].x,&a[i].l,&a[i].y,&a[i].r),a[i].x++,a[i].l++;
b[0]=c[n+1]=(node){0,0,(int)1e9,(int)1e9};int ans=0;
for(int i=1;i<=n;i++)b[i]=get(b[i-1],a[i]);
for(int i=n;i>=1;i--)c[i]=get(c[i+1],a[i]);
for(int i=1;i<=n;i++)ans+=get(b[i-1],c[i+1]).gett();
ans-=gan().gett()*(n-1);cout<<ans<<endl;
}
return 0;
}
Feel like a zz
T3. Beautiful melody
Enumerate strings, and then enumerate their multiples. Hash to determine whether they are legal. Complexity \ (n^2\ln n \)
It can be optimized to \ (n^2 \) by marking, but the constant is too small
T4. Base station construction
Undirected graph ternary ring board, find out the ring and judge
Take the hash table and store it violently. Find that there is just enough space, and then give the answer at the end
Complexity \ (m\sqrt m \), with extra large constant
#include <bits/stdc++.h>
using namespace std;
#define int unsigned int
#define pir pair<int,int>
const int N=50050,M=200050;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
struct node{
int from,to,next;
}a[2*M];
int head[N],mm=1;
inline void add(int x,int y)
{
a[mm].from=x;a[mm].to=y;
a[mm].next=head[x];head[x]=mm++;
}
unordered_map <int,int> mp;
int c[450*N][2],n,m,w[N],tot,id[450*N];
inline int ganhash(int x,int y)
{
return x*50001+y;
}
inline void ganid(int x,int y,int z)
{
int idd;
if(mp.find(ganhash(x,y))!=mp.end())idd=mp[ganhash(x,y)];
else if(mp.find(ganhash(y,x))!=mp.end())idd=mp[ganhash(y,x)];
else idd=++tot,mp.insert(make_pair(ganhash(x,y),idd)),id[idd]=ganhash(x,y);
if(!c[idd][0])c[idd][0]=z;
else if(!c[idd][1])
{
c[idd][1]=z;if(w[c[idd][0]]<w[c[idd][1]])swap(c[idd][0],c[idd][1]);
}
else
{
if(w[z]<=w[c[idd][1]])return;
else if(w[z]<=w[c[idd][0]])c[idd][1]=z;
else c[idd][1]=c[idd][0],c[idd][0]=z;
}
}
inline void gan(int x,int y,int z)
{
ganid(x,y,z);ganid(x,z,y);
ganid(y,z,x);
}
int fr[M],to[M],du[N],v[N];
signed main()
{
freopen("station.in","r",stdin);
freopen("station.out","w",stdout);
cin>>n>>m;int sum=0;
for(int i=1;i<=n;i++)w[i]=read();
for(int i=1;i<=m;i++)
{
fr[i]=read(),to[i]=read();
du[fr[i]]++;du[to[i]]++;
}
for(int i=1;i<=m;i++)
{
int x=fr[i],y=to[i];
if(du[x]<du[y]||(du[x]==du[y]&&x<y))swap(x,y);
add(x,y);
}
for(int x=1;x<=n;x++)
{
for(int i=head[x];i;i=a[i].next)v[a[i].to]=x;
for(int i=head[x];i;i=a[i].next)
{
int y=a[i].to;
for(int j=head[y];j;j=a[j].next)
{
int z=a[j].to;
if(v[z]==x)gan(x,y,z);
}
}
}
int ans=0;
for(int i=1;i<=tot;i++)
{
if(!(w[c[i][0]]*w[c[i][1]]))continue;
int x=id[i]/50001,y=id[i]%50001;
ans=max(ans,w[c[i][0]]*w[c[i][1]]+(w[x]+1)*(w[y]+1));
}
cout<<ans<<endl;
return 0;
}
Examination summary
Thinking must be realized. Don't regret the questions you can do
Don't look at the questions. It's time-consuming and easy to panic. Think about the questions. Don't hesitate