week2OJ赛
1-1
题目 行列式
测试样例输入：
3
3
1 -2 -1
0 3 2
3 1 -1
3
0 3 2
1 -2 -1
3 1 -1
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
测试样例输出：
522133271
8
0
思路：
emmm递归只拿了2分
code:
#include<stdio.h>
#define N 10
long long getA(long long arcs[N][N],int n)//按第一行展开计算|A|
{
if(n==1)
return arcs[0][0];
long long ans = 0;
long long temp[N][N];
int i,j,k;
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
for(k=0;k<n-1;k++)
{
temp[j][k]=arcs[j+1][(k>=i)?k+1:k];
}
}
int t=getA(temp,n-1);
if(i%2==0)
ans+=arcs[0][i]*t;
else
ans-=arcs[0][i]*t;
}
return ans;
}
int main()
{
long long arcs[N][N];
int i,j;
int n,t;
scanf("%d",&t);
for (int x=0;x<t;x++)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%lld",&arcs[i][j]);
}
}
long long result=getA(arcs,n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
arcs[i][j]=0;
printf("%lld\n",result%(0x1f1f1f1f));
}
return 0;
}
1-2
题目 三连
思路
对呀对呀，先累加前缀和数组，然后对于筛掉总和不能除以3的，对于可以整除3的数组，寻找等于1/3总和的项数…怎么就每分呢，生气气
code
#include <stdio.h>
#include <unordered_map>
//#include <map>
#define N 100000
using namespace std;
int subarraySum(long long* nums,int len,long long k)
{
unordered_map<int, int> mp;//前缀和-k，次数
//map<int, int> mp;
mp[0] = 1;
int count = 0;
for (int i=0;i<len;i++)
{
if (mp.find(nums[i]-k)!= mp.end())
{
count+=mp[nums[i]-k];
}
mp[nums[i]]++;
}
return count;
}
int main()
{
int n=0,i,A[N];
long long sum[N];
scanf("%d",&n);
for (i=0;i<n;i++)
{
scanf("%d",&A[i]);
if (i==0)
sum[i]=A[i];
else
sum[i]=A[i]+sum[i-1];
}
if (sum[n-1]%3!=0)
printf("0");
else
{
int num=subarraySum(sum,n,sum[n-1]/3);
printf("%d",num/3);
}
return 0;
}
1-3 照亮街道
思路
这题我会嘿嘿，注意输入不一定是整数，注意头尾灯
code
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
vector<double> line;//记录路灯坐标
vector<double> diff;//差分后距离
int main()
{
int n,l,i;
double temp;
bool flag[2]={0,0};//标志首尾
scanf("%d %d",&n,&l);
for (i=0;i<n;i++)
{
scanf("%lf",&temp);
line.push_back(temp);
if (temp==0)
flag[0]=1;
if (temp==l)
flag[1]=1;
}
sort(line.begin(),line.end());
if (flag[0]==0)//对于首尾未出现灯的情况，把最近一盏灯到首/尾的距离加入差分的（*2是因为这个距离本来是不用两盏灯共有再/的，但为了方便后续排序而加）
diff.push_back(line[0]*2);
if (flag[1]==0)
diff.push_back((l-line[line.size()-1])*2);
for (i=1;i<n;i++)
{
temp=line[i]-line[i-1];
diff.push_back(temp);
}
sort(diff.begin(),diff.end());
printf("%.2f",diff[diff.size()-1]*0.5);
return 0;
}
1-4 宝宝抢糖果
题目
思路
我是组合数累加求的，看有大佬好像推导发现规律是f(n)=f(n-1)+f(n-2)，类比爬楼梯？这一看就是我刷题刷少了
code
#include <stdio.h>
int compose(int a,int b)
{
int up=1,down=1;
if (b==0)
return 1;
else
{
if (b >a/2)
b=a-b;
int temp=b;
while(temp>1)
{
down*=temp;
temp--;
}
while(b>0)
{
up*=a;
a--;b--;
}
}
return (up/down);
}
int main()
{
int num1=0,num2=0,result=0,n=0;
scanf("%d",&n);
num1=n;
while(num1>=(n%2))
{
result+=compose(num1+num2,num2);
num1-=2;num2++;
}
printf("%d",result);
return 0;
}
1-5 N的M次方
题目
思路
为什么又是WA呢，我不理解
我高精度乘法模拟取后三位不行？我还对逆序大小做了细细研究呢
算了，看正确AC题解，好像先求逆序数，然后相乘对1000取余会好做许多
code
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
bool cmp(char x,char y)
{
return x>y;
}
int main()
{
char s[10]={'\0'};
int A[3]={0},n=0,i,col,j,temp,flag[2]={0},num=0;
long long invert=0;
scanf("%s",&s);
A[0]=s[strlen(s)-1]-'0';
if (strlen(s)>=2)
A[1]=s[strlen(s)-2]-'0';
n=A[0]+A[1]*10;
if (A[1]>A[0]||A[1]==0)
invert=n;
else
invert=A[1]+A[0]*10;
for (i=0;i<invert-1;i++)
{
col=0;
for (j=0;j<3;j++)
{
if (A[1]!=0)
flag[0]=1;
if (A[2]!=0)
flag[1]=1;
temp=n*A[j]+col;
A[j]=temp%10;
col=temp/10;
}
}
for (i=0;i<3;i++)
{
if (i==0&&flag[1]==0)
continue;
if (i==1&&flag[0]==0)
continue;
printf("%d",A[2-i]);
}
return 0;
}
成绩
32/50，加油
优秀题解
第1题优解
/*
*/
第2题优解
第5题优解
