20250316 OPPO笔试

#include <iostream>#include <vector>#include <string>using namespace std;
const int MOD = 1e9 + 7;
int main() {
  int n;string s;cin >> n >> s;
  long long sum_known = 0;
  vector<int> unknown_positions;

  for (int i = 0; i < n; ++i) {
	  if (s[i] == '?') {
		  unknown_positions.push_back(i);
	  } else {
		  sum_known += s[i] - '0';
	  }
  }

  int s_rem = sum_known % 3;
  int target_rem = (3 - s_rem) % 3;

  if (unknown_positions.empty()) {
	  cout << (s_rem == 0 ? 1 : 0) << endl;
	  return 0;
  }

  bool first_is_unknown = (unknown_positions[0] == 0);

  vector<long long> dp(3, 0);

  if (first_is_unknown) {
	  // 处理第一个问号(不能为0)
	  dp[0] = 3; // 可选的余数0的数字:3,6,9
	  dp[1] = 3; // 余数1:1,4,7
	  dp[2] = 3; // 余数2:2,5,8

	  // 处理剩余问号
	  for (int i = 1; i < unknown_positions.size(); ++i) {
		  vector<long long> new_dp(3, 0);
		  for (int prev = 0; prev < 3; ++prev) {
			  // 转移公式:dp[prev]表示前 i-1 个数值为prev的可能组合数,(prev + 0) % 3 表示prev转移为(prev + 0)的组合数。
			  new_dp[(prev + 0) % 3] = (new_dp[(prev + 0) % 3] + dp[prev] * 4) % MOD;
			  new_dp[(prev + 1) % 3] = (new_dp[(prev + 1) % 3] + dp[prev] * 3) % MOD;
			  new_dp[(prev + 2) % 3] = (new_dp[(prev + 2) % 3] + dp[prev] * 3) % MOD;
		  }
		  dp = new_dp;
	  }
  } else {
	  // 所有问号都不是首位
	  dp[0] = 1;
	  for (int pos : unknown_positions) {
		  vector<long long> new_dp(3, 0);
		  for (int prev = 0; prev < 3; ++prev) {
			  new_dp[(prev + 0) % 3] = (new_dp[(prev + 0) % 3] + dp[prev] * 4) % MOD;
			  new_dp[(prev + 1) % 3] = (new_dp[(prev + 1) % 3] + dp[prev] * 3) % MOD;
			  new_dp[(prev + 2) % 3] = (new_dp[(prev + 2) % 3] + dp[prev] * 3) % MOD;
		  }
		  dp = new_dp;
	  }
  }
  cout << dp[target_rem] % MOD << endl;
  return 0;
}
#OPPO笔试##笔试#
全部评论

相关推荐

嵌入式开发工程师职位名称:嵌入式开发工程师&nbsp;&nbsp;所属部门:硬件研发部&nbsp;&nbsp;工作地点:沈阳&nbsp;&nbsp;薪资范围:15-20K/月(13薪+绩效奖金)&nbsp;&nbsp;岗位职责:&nbsp;&nbsp;1.&nbsp;固件开发:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;基于Linux/FreeRTOS开发边缘计算单元(Jetson&nbsp;Nano/RK3588)的底层驱动,支持多传感器(摄像头、红外测温、麦克风阵列)数据采集。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;优化硬件资源占用(内存&amp;lt;500MB,CPU利用率&amp;lt;70%)。&nbsp;&nbsp;2.&nbsp;低功耗优化:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;实现动态电压频率调整(DVFS),待机功耗&amp;lt;5W。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;设计离线缓存机制(存储30天数据),支持断网环境下的本地决策。&nbsp;&nbsp;3.&nbsp;通信协议开发:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;开发设备与云端的数据传输协议(MQTT/CoAP),确保数据同步延迟&amp;lt;1秒。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;适配工业通信协议(如Modbus&nbsp;RTU/TCP),支持PLC设备联动控制。&nbsp;&nbsp;4.&nbsp;故障排查:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;分析硬件异常日志(如SPI通信超时、DMA溢出),提出改进方案。&nbsp;&nbsp;任职要求:&nbsp;&nbsp;1.&nbsp;教育背景:本科及以上学历,计算机、电子工程、通信工程等相关专业。&nbsp;&nbsp;2.&nbsp;经验要求:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;3年以上嵌入式开发经验,熟悉ARM/Linux开发环境。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;有边缘计算设备(如智能摄像头、工业网关)开发经验。&nbsp;&nbsp;3.&nbsp;技术能力:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;精通C/C++,熟悉Python脚本开发。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;掌握Linux内核裁剪、设备树(Device&nbsp;Tree)配置、驱动开发。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;熟悉RTOS系统(FreeRTOS、Zephyr)实时任务调度机制。&nbsp;&nbsp;4.&nbsp;加分项:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;有FPGA开发经验(如Xilinx&nbsp;Zynq系列)。&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-&nbsp;熟悉硬件安全机制(Secure&nbsp;Boot、TrustZone)。&nbsp;
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务