牛客多校第八场C CDMA (技巧构造）
题意：
输入整数m（ m∈2k ∣ k=1,2,⋯,10），构造一个由1和-1组成的m×m矩阵，要求对于任意两个不同的行的内积为0。
题解：
我觉得这个思路太优秀了，我自己想不到。具体说明看代码我的注释就好、
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int a[1200][1200];
//k的维度代表基底矩阵的那个A，而n代表着当前矩阵的维度
void solve(int k,int n,int m)
{
if(n==(m<<1))//这样就说明前一秒求得是m维度
return;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i<n/2||j<n/2)
{
a[i][j]=a[i%k][j%k];
}
else
a[i][j]=-a[i%k][j%k];//这种情况代表右下角
}
}
solve(k<<1,n<<1,m);
}
int main()
{
int m;
scanf("%d",&m);
a[0][0]=1,a[0][1]=1,a[1][0]=1,a[1][1]=-1;
solve(2,4,m);
for(int i=0;i<m;i++)
{
for(int j=0;j<m;j++)
{
cout<<a[i][j];
if(j!=m-1)
cout<<" ";
else
cout<<endl;
}
}
return 0;
}
牛客多校第八场 Beauty Values(贡献法）
题意：输入整数n，再输入n个整数a1,a2,⋯ ,an，表示一段序列,求序列的所有子区间里面不同数字之和。
枚举每个数字，算出每个数字对答案的贡献，最后把答案累加起来。qq[a]记录a的上一个位置，则a对答案的贡献是(i-qq[a])*(n-i+1)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll n,a,qq[maxn];
int main()
{
while(~scanf("%d",&n)) {
for(int i=1;i<=n;i++)
qq[i]=0;
ll ans=0;
for(int i=1;i<=n;i++) {
scanf("%lld",&a);
ans+=(i-qq[a])*(n-i+1);
qq[a]=i;
}
printf("%lld\n",ans);
}
return 0;
}
牛客多校第二场 Second Large Rectangle
https://ac.nowcoder.com/acm/contest/882/H
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1005][1005];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
scanf("%1d", &a[i][j]);
a[i][j] += a[i][j] * a[i-1][j];
//预处理a[i][j]为该点上方路连续1的最大值
}
}
int maxarea = 0, secarea = 0;
//从右下角开始往左、上遍历
for(int i = n; i >= 1; i--)
{
for(int j = m; j >= 1; j--)
{
int height = a[i][j];
for(int k = j; k >= 0; k--)
{
if(a[i][k] == 0)//剪枝
{
break;
}
if(height * j <= secarea)//剪枝
{
break;
}
height = min(height, a[i][k]);
int area = height * (j-k+1);
if(area >= maxarea)
{
secarea = maxarea;
maxarea = area;
}
else if(area >= secarea)
{
secarea = area;
}
}
}
}
printf("%d\n", secarea);
return 0;
}
https://ac.nowcoder.com/acm/contest/949/D
小阳买水果
思维技巧题小阳买水果逆序数递推nyoj 177求逆序数
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
struct node{
int num,pos;
}e[maxn];
bool cmp(node a,node b)//排序
{
if(a.num==b.num)
return a.pos>b.pos;//如果前缀和相等，则按照位置从大到小排
return a.num<b.num;//前缀和从小到大排序
}
/*求一下前缀和num，即要求满足num[x]-num[y]>0的最大的(x-y)，那么我们从小到大排个序
从左到右扫一遍，记录num的最小的position，每次拿当前的position减去最小的position来更新一下结果，
排序的时候要考虑一下num[0]，即不包含任何一个数的num[0]（值为0）;
*/
int main()
{
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
e[i].num=x+e[i-1].num;//前缀和
e[i].pos=i;//位置
}
n++;
sort(e+1,e+n+1,cmp);
int minx=n;
int ans=0;
for(int i=1;i<=n;i++)
{
minx=min(minx,e[i].pos);
if(e[i].pos>minx)
ans=max(ans,e[i].pos-minx);
}
printf("%d\n",ans);
return 0;
}
逆序数
HDU6318
解答：求逆序数板子，ans即为一个序列的逆序对（逆序数）的个数。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define ll long long
#define int ll
#define lowbit(x) (x&(-x))
int c[N];
struct node
{
int v,id;
bool operator < (node b)
{
return (v<b.v)||(v==b.v&&id<b.id); //从小到大排序
}
} node[N];
int n;
void add(int i)
{
while(i<=n)
{
c[i]++;
i+=lowbit(i);
}
}
long long sum(int i)
{
long long res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
signed main()
{
ll x,y;
while(~scanf("%lld%lld%lld",&n,&x,&y))
{
memset(c,0,sizeof(c));
int a;
for(int i=1; i<=n; i++)
{
scanf("%lld",&a);
node[i].id=i;
node[i].v=a;
}
sort(node+1,node+1+n);
ll ans=0;
for(int i=1; i<=n; i++)
{
add(node[i].id); //离散化结果—— 下标等效于数值
ans+=i-sum(node[i].id); //得到之前有多少个比你大的数（逆序对）
}
printf("%lld\n",ans*min(x,y));
}
return 0;
}
递推
p1028数的计数https://www.luogu.org/problemnew/show/P1028
题目的意思是寻找自然数，在其左边添加数字，其数字不超过该数字的一半。
主要就是找规律，多写几项出来就可以找到递推式，主要是不要被困难吓倒。
n=0,n=1时，答案显然是1 n=2, ans=2; n=3,ans=2 n=4,ans=4; n=5,ans=4 n=6,ans=6; n=7,ans=6
相信大家也发现了，2n与2n+1(n为非负整数)的答案是一样的 这就是第一个规律
然后我们以n=8为例，手动模拟一下
一共有10组解
8、18、28、38、48
128、138、148、248
1248
n%2==0时 f(n)=f(n-1)+f(n/2)
n%2==1时 f(n)=f(n-1)
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int f[1005];
int main()
{
int n;
cin>>n;
f[0]=1,f[1]=1,f[2]=2,f[3]=2;
for(int i=4;i<=n;i++)
{
if(i%2==0)
f[i]=f[i-1]+f[i/2];
else
f[i]=f[i-1];
}
cout<<f[n]<<endl;
return 0;
}
-
nyoj 177求逆序数
描述
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。
比如 1 3 2 的逆序数就是1。
输入
第一行输入一个整数T表示测试数据的组数（1<=T<=5)
每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000）
随后的一行共有N个整数Ai(0<=Ai<1000000000)，表示数列中的所有元素。
数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。
输出
输出该数列的逆序数
样例输入
2
2
1 1
3
1 3 2
样例输出
1
利用归并排序，可以减小复杂度
#include <stdio.h>
#include <string.h>
long long a[1000005];
long long b[1000005];
long long count;
void Merge(long long *a,int L,int mid,int R)
{
int k=L;
int i=L,j=mid+1;
while(i<=mid && j<=R)
{
//较小的元素，存入temp临时数组中
if(a[i]<=a[j])
b[k++]=a[i++];
else//出现逆序对
{
b[k++]=a[j++];
count+=mid-i+1;
}
}
//假如第1个有序区仍有剩余，则直接全部复制到 b数组
while(i<=mid)
b[k++]=a[i++];
//同理，有剩余则放到 b数组
while(j<=R)
b[k++]=a[j++];
//将排好的序列，重新放到原数组的 L和 R区间
for(int t=L;t<=R;t++)
a[t]=b[t];
}
void MergeSort(long long *a,int L,int R)
{
if(L<R)
{
int mid = (L+R)/2;
MergeSort(a,L,mid);
MergeSort(a,mid+1,R);
Merge(a,L,mid,R);
}
}
int main()
{
int T,N,i;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(i=0;i<N;i++)
scanf("%lld",&a[i]);
count=0;
MergeSort(a,0,N-1);
printf("%lld\n",count);
}
return 0;
}
p1424 小鱼的航程（简单数学思考）https://www.luogu.org/problemnew/show/P1424
首先计算整周的天数，然后判断一下剩余部分是否有休息日即可。
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int x;
ll n;
cin>>x>>n;
ll t=n/7*5;
ll temp=n%7;//剩余的天数
if(temp>0)
{
if(x==7||temp+x==7)//如开始为周日肯定只休息一天；如r+x==7即最后一天为周六，也休息一天,计算这个还要算当天，别忘了
{
temp-=1;
}
else if(temp+x>=8) //最后一天已过周日，休息两天
{
temp-=2;
}
}
cout<<(t+temp)*250<<endl;
return 0;
}
差分法
https://www.luogu.org/problemnew/show/P1047 p1047校门外的树
这是一个巧妙的办法，这就类似于区间合并吧感觉。可以降低复杂度吧。由于移走的树包括端点，所以在a[rr+1]处--，这样到达这里时，才会让num<=0，这样才方便计算。
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int a[10005];
/*500 3
150 300
100 200
470 471
*/
int main()
{
int n,m;
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
int ll,rr;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&ll,&rr);
a[ll]++;
a[rr+1]--;
}
int ans=0,num=0;
for(int i=0;i<=n;i++)//题目说的是0~L种树，，，请细心点。
{
num+=a[i];
if(num<=0)
ans++;
}
cout<<ans<<endl;
return 0;
}
洛谷p1553 数字反转升级版
https://www.luogu.org/problemnew/show/P1553
这道题题目不难，比较考细节，一共20个测试点，我总有三个过不了。参考了别人的去前导0，去后缀0的方法，还是蛮有收获
#include<bits/stdc++.h>
using namespace std;
char a[100];
int main()
{
int pos=-1;
int cnt=0;
cin>>a;
int len=strlen(a);
for(int i=0; i<len; i++)
{
if(a[i]>='0'&&a[i]<='9')
cnt++;//记录第一个数长度
else //遇到符号，记录，跳出
{
pos=i;
break;
}
}
int x=cnt;//记下第一个数末后一个的位置，也就是符号的位置，如果是分数或小数就要用
cnt--;//前面数字的最后一个索引
while(a[cnt]=='0'&&cnt>0)
cnt--;//去除多余前导0；
for(int i=cnt; i>=0; i--) //输出第一个数
cout<<a[i];
if(pos==-1)
return 0;//无符号return 0
else if(a[pos]=='%')
{
cout<<a[pos];
return 0;
}
else
cout<<a[pos];//其他继续
int m=len-1;
while(a[x+1]=='0'&&x<m-1)
x++;//去除末尾0
while(a[m]=='0'&&m>x+1)
m--; //去除多余前导0
for(int i=m; i>x; i--) //输出第二个数
cout<<a[i];
return 0;
}